scientific article; zbMATH DE number 512919

MaRDI QIDQ4281631zbMATH OpenFDO

Authors Elias Dahlhaus

Publication date 20 June 1994

zbMATH Keywords

all-to-all distance problemgraph algorithmmatrix multiplicationparallel algorithms

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs
• An optimal algorithm to solve the all-pair shortest path problem on interval graphs
• Unified all-pairs shortest path algorithms in the chordal hierarchy

Cited in

(5)

• Unified all-pairs shortest path algorithms in the chordal hierarchy
• 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
• 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:

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