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

DOI10.1016/j.dam.2006.06.008zbMath1113.68070OpenAlexW2091466470MaRDI QIDQ868392

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

bipartite permutation graphpermutation graphall pairs shortest pathsunit interval graph

Mathematics Subject Classification ID

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

Uses Software

• Algorithm 97

Cites Work

• Solving the all-pairs-shortest-length problem on chordal bipartite graphs
• Simple linear time recognition of unit interval graphs
• Solving the shortest-paths problem on bipartite permutation graphs efficiently
• Unified all-pairs shortest path algorithms in the chordal hierarchy
• Improved 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)
• Solving the all-pair shortest path query problem on interval and circular-arc graphs
• O(1) QUERY TIME ALGORITHM FOR ALL PAIRS SHORTEST DISTANCES ON INTERVAL GRAPHS
• An O(n 3 (loglogn/logn)5/4) Time Algorithm for All Pairs Shortest Paths
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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