Journal of the ACM Bibliography
Greg N. Frederickson. Planar
graph decomposition and all pairs shortest paths. Journal of the
ACM, 38(1):162-204, January 1991.
[BibTeX entry]
Categories and Subject Descriptors:
E.1 [Data Structures] -- graphs; F.2.2
[Analysis of Algorithms and Problem Complexity]:
Nonnumerical Algorithms and Problems -- computations on discrete
structures; G.2.2 [Discrete Mathematics]: Graph
Theory -- graph algorithms, network problems
General Terms:
Algorithms, Theory
Additional Key Words and Phrases:
All pairs shortest paths, approximation algorithm, compact routing
table, graph embedding, NP-completeness, outerplanar graph, planar
graph, succinct encoding
Selected papers that cite this one
- Adam L. Buchsbaum, Rajamani Sundar, and Robert E. Tarjan. Data-structural
bootstrapping, linear path compression, and catenable heap-ordered
double-ended queues. SIAM Journal on Computing,
24(6):1190-1206, December 1995.
- Edith Cohen. Efficient parallel
shortest-paths in digraphs with a separator decomposition.
Journal of Algorithms, 21(2):331-357, September 1996.
- G. N. Frederickson. Searching
among intervals and compact routing tables.
Algorithmica, 15(5):448-466, May 1996.
- Greg N. Frederickson. Using cellular
graph embeddings in solving all pairs shortest paths problems.
Journal of Algorithms, 19(1):45-85, July 1995.
- Dimitris J. Kavvadias, Grammati E. Pantziou, Paul G. Spirakis, and
Christos D. Zaroliagis. Hammock-on-ears
decomposition: A technique for the efficient parallel solution of
shortest paths and other problems. Theoretical Computer
Science, 168(1):121-154, 10 November 1996.
Selected references
- Brenda S. Baker. Approximation algorithms for
NP-complete problems on planar graphs (preliminary version). In
24th Annual Symposium on Foundations of Computer Science,
pages 265-273, Tucson, Arizona, 7-9 November 1983. IEEE.
- Greg N. Frederickson. Implicit data structures for
the dictionary problem. Journal of the ACM,
30(1):80-94, January 1983.
- Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in
improved network optimization algorithms. Journal of the
ACM, 34(3):596-615, July 1987.
- John Hopcroft and Robert Tarjan. Efficient planarity testing.
Journal of the ACM, 21(4):549-568, October 1974.
- Stephen Warshall. A
theorem on Boolean matrices. Journal of the ACM,
9(1):11-12, January 1962.
Shortcuts: