Using Cellular Graph Embeddings in Solving All Pairs Shortest Paths Problems

DOI10.1006/JAGM.1995.1027MaRDI QIDQ4840219zbMATH OpenOpenAlexFDO

Authors Greg N. Frederickson

Publication date 11 April 1996

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/f9e21b22da70996ce1d1ba33f28bb62c46920b77

zbMATH Keywords

succinct encoding

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• Planar graph decomposition and all pairs shortest paths
• Efficient parallel algorithms for shortest paths in planar graphs
• All pairs shortest paths for graphs with small integer length edges
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• A new approach to dynamic all pairs shortest paths

Cited in

(5)

• Algorithmic graph embeddings
• Searching among intervals and compact routing tables
• Planar graph decomposition and all pairs shortest paths
• Faster algorithms for shortest path and network flow based on graph decomposition
• A face cover perspective to _1 embeddings of planar graphs

This page was built for publication: Using Cellular Graph Embeddings in Solving All Pairs Shortest Paths Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4840219)