Title :
Shortest path problems in planar graphs
Author :
Frederickson, Greg N.
Abstract :
Graph decomposition and data structures techniques are presented that make possible faster algorithms for shortest paths in planar graphs. Improved algorithms are presented for the single source problem, the all pairs problem, and the problem of finding a minimum cut in an undirected graph.
Keywords :
Character generation; Costs; Data structures; Iterative algorithms; Particle separators; Partitioning algorithms; Shortest path problem;
Conference_Titel :
Foundations of Computer Science, 1983., 24th Annual Symposium on
Conference_Location :
Tucson, AZ, USA
Print_ISBN :
0-8186-0508-1
DOI :
10.1109/SFCS.1983.69
