Unified all-pairs shortest path algorithms in the chordal hierarchy
From MaRDI portal
The authors show that solving the all-pairs shortest path (APSP) problem for a chordal graph \(G\) is a two-step process: (1) Compute \(G^2\). (2) Find the vertex pairs of distance three or more. The main result is that knowing \(G^2\), the APSP problem for chordal graphs can be solved in \(O(n^2)\) time (optimal time). Parallel algorithms are also considered.
Recommendations
Cites work
- 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 ordering of dense 0--1 matrices
- Doubly Lexical Orderings of 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
- 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?)
- 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
(9)- All-pairs-shortest-length on strongly chordal graphs
- A survey of the all-pairs shortest paths problem and its variants in graphs
- Solving the all-pairs-shortest-length problem on chordal bipartite graphs
- On the union of intermediate nodes of shortest paths
- scientific article; zbMATH DE number 512919 (Why is no real title available?)
- scientific article; zbMATH DE number 2044927 (Why is no real title available?)
- An all-pairs shortest path algorithm for bipartite graphs
- Diameter determination on restricted graph families
- \(O(1)\) query time algorithm for all pairs shortest distances on permutation graphs
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)
