O(1) query time algorithm for all pairs shortest distances on permutation graphs

DOI10.1016/J.DAM.2006.06.008MaRDI QIDQ868392zbMATH OpenOpenAlexFDO

Authors Alan P. Sprague

Publication date 2 March 2007

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

Full work available at URL https://doi.org/10.1016/j.dam.2006.06.008

zbMATH Keywords

all pairs shortest pathsbipartite permutation graphpermutation graphunit interval graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs
• O(1) QUERY TIME ALGORITHM FOR ALL PAIRS SHORTEST DISTANCES ON INTERVAL GRAPHS
• Distance Labeling for Permutation Graphs
• Some Efficient Algorithms for Permutation Graphs
• scientific article; zbMATH DE number 512919

Cites work

• An O(n 3 (loglogn/logn)5/4) Time Algorithm for All Pairs Shortest Paths
• An optimal algorithm to solve the all-pair shortest path problem on interval graphs
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 1156661 (Why is no real title available?)
• scientific article; zbMATH DE number 913360 (Why is no real title available?)
• scientific article; zbMATH DE number 2191997 (Why is no real title available?)
• Improved algorithm for all pairs shortest paths
• O(1) QUERY TIME ALGORITHM FOR ALL PAIRS SHORTEST DISTANCES ON INTERVAL GRAPHS
• Simple linear time recognition of unit interval graphs
• Solving the all-pair shortest path query problem on interval and circular-arc graphs
• Solving the all-pairs-shortest-length problem on chordal bipartite graphs
• Solving the shortest-paths problem on bipartite permutation graphs efficiently
• Unified all-pairs shortest path algorithms in the chordal hierarchy

Cited in

(2)

• An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs
• O(1) QUERY TIME ALGORITHM FOR ALL PAIRS SHORTEST DISTANCES ON INTERVAL GRAPHS

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication: \(O(1)\) query time algorithm for all pairs shortest distances on permutation graphs

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