O(1) QUERY TIME ALGORITHM FOR ALL PAIRS SHORTEST DISTANCES ON INTERVAL GRAPHS

DOI10.1142/S0129054199000320zbMath1320.05131MaRDI QIDQ5249020

Alan P. Sprague, Tadao Takaoka

Publication date: 29 April 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

interval graphsunit interval graphscircular arc graphsAPSP

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (2)

\(O(1)\) query time algorithm for all pairs shortest distances on permutation graphs ⋮ Parameterized complexity of diameter

Cites Work

• Unnamed Item
• Simple linear time recognition of unit interval graphs
• Some parallel algorithms on interval graphs
• An Efficient Parallel Biconnectivity Algorithm
• An optimal algorithm to solve the all-pair shortest path problem on interval graphs
• Solving the all-pair shortest path query problem on interval and circular-arc graphs

This page was built for publication: O(1) QUERY TIME ALGORITHM FOR ALL PAIRS SHORTEST DISTANCES ON INTERVAL GRAPHS