Extremal Paths in Graphs
Foundation, Search Strategies, and Related Topics
Published on 10. June 1997
Book
Hardback
480 pages
978-3-05-501658-5 (ISBN)
Description
The main topic of this text is the search for optimal paths in graphs if the given cost function for paths satisfies very weak conditions. Moreover, the author studies structural properties of cost measures, and quotes many combinatorial results concerning paths in graphs.
More details
Content
Structural properties of cost functions for paths in graphs; generalized principles of order preservatioin, generalized Bellman principles; combinatorial results on paths in graphs; the search for optimal paths in graphs - generalized versions of the Dijkstra algorithm and of the Ford-Bellman algorithm; optimal path problems and their solutions in special graphs, for example in planar or in random graphs; hard path problems, for example the Travelling Salesman problem.