Extremal paths in graphs

More about the book

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 and 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, and order preservation of cost functions.