Unified all-pairs shortest path algorithms in the chordal hierarchy

DOI10.1016/S0166-218X(96)00103-5MaRDI QIDQ1364781zbMATH OpenOpenAlexFDO

Authors O. Diekmann

Publication date 28 August 1997

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

algorithmschordal graphall-pairs shortest path

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Recommendations

• Solving the all-pairs-shortest-length problem on chordal bipartite graphs
• All-pairs-shortest-length on strongly chordal graphs
• Estimating all pairs shortest paths in restricted graph families: a unified approach
• scientific article; zbMATH DE number 2044927

Cites work

• scientific article; zbMATH DE number 1003284 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4202291 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 139779 (Why is no real title available?)
• scientific article; zbMATH DE number 512919 (Why is no real title available?)
• An algorithm for finding all shortest paths using \(N^{2\cdot 81}\) infinite-precision multiplications
• An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
• An optimal algorithm to solve the all-pair shortest path problem on interval graphs
• Doubly Lexical Orderings of Matrices
• Doubly lexical ordering of dense 0--1 matrices
• Efficient algorithms for shortest distance queries on special classes of polygons
• Efficient algorithms for solving systems of linear equations and path problems
• Highly parallelizable problems on sorted intervals
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Recursive Graphs, Recursive Labelings and Shortest Paths
• Shortest-path problem is not harder than matrix multiplication
• Solving the all-pair shortest path query problem on interval and circular-arc graphs

Cited in

(7)

• A survey of the all-pairs shortest paths problem and its variants in graphs
• Diameter determination on restricted graph families
• Solving the all-pairs-shortest-length problem on chordal bipartite graphs
• \(O(1)\) query time algorithm for all pairs shortest distances on permutation graphs
• scientific article; zbMATH DE number 2044927 (Why is no real title available?)
• An all-pairs shortest path algorithm for bipartite graphs
• On the union of intermediate nodes of shortest paths

This page was built for publication: Unified all-pairs shortest path algorithms in the chordal hierarchy

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