Extremal Paths in Graphs: Foundations, Search Strategies, and Related Topics

Front Cover
John Wiley & Sons, Incorporated, Jan 1, 1997 - Mathematics - 480 pages
0 Reviews
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.

From inside the book

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Introduction
13
Path functions
21
Combinatorial results about paths in graphs
123
Copyright

5 other sections not shown

Common terms and phrases

Bibliographic information