Extremal Paths in Graphs: Foundations, Search Strategies, and Related Topics
This book examines the central problem of searching for optimal paths in graphs--the search for the shortest connection from one place to another one in a city, for example. It investigates generalized versions of the Dijkstra algorithm & the Ford-Bellman algorithm. These generalized search strategies find paths with minimum or almost minimum costs even if the cost function is not computed by adding costs of the edges of a path. The book describes many types of optimal path problems including the search for optimal paths in random graphs or NP-complete optimal path problems like the Traveling Salesman Problem. It also studies structural properties of cost measures for paths in graphs; in particular, generalized versions of additivity, Bellman properties, & order preservation of cost functions.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Combinatorial results about paths in graphs
5 other sections not shown
acyclic path arc function assume assumption Bellman path Best-First search Breadth-First search C-minimal path C-optimal C-value candidates condition connected Consequently construct cost function cost measure decision function define Definition describe digraph Q DIJKSTRA-BFS Dijkstra's algorithm edge equation equivalent example exists expanded following assertions following is true following properties FORD-BELLMAN formulate function H Given a digraph goal nodes goal path graph Q Hamiltonian cycle Hence heuristic function i-j-path implies Lemma Let H Let Q locally finite digraph lower bound matrix matrix multiplication means Moreover node function node injective cycle order preserving oriented Bellman property output path function path P(v path Q paths in graphs planar graphs prefix monotone prefix oriented Bellman Proof property of type Pt(v Pt+i(v recursively Remark result s-u-path search strategy side constraints solved subgraph Subsection SUMh Theorem Traveling Salesman Problem triangle inequality tth iteration undirected graph V,TZ