An optimal algorithm to solve the all-pair shortest path problem on interval graphs

DOI10.1002/net.3230220103zbMath0761.90096OpenAlexW2082795813MaRDI QIDQ3989542

R. Ravi, C. Pandu Rangan, Madhav V. Marathe

Publication date: 28 June 1992

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230220103

zbMATH Keywords

perfect graphsinterval graphsneighborhood treeunweighted all-pair shortest path

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (13)

Computing the average distance of an interval graph ⋮ Solving the all-pairs-shortest-length problem on chordal bipartite graphs ⋮ Efficient algorithms for centers and medians in interval and circular-arc graphs ⋮ A survey of the all-pairs shortest paths problem and its variants in graphs ⋮ An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications ⋮ Unified all-pairs shortest path algorithms in the chordal hierarchy ⋮ \(O(1)\) query time algorithm for all pairs shortest distances on permutation graphs ⋮ Algorithms for interval structures with applications ⋮ Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph ⋮ Unnamed Item ⋮ Algorithms for Interval Structures with Applications ⋮ An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs ⋮ O(1) QUERY TIME ALGORITHM FOR ALL PAIRS SHORTEST DISTANCES ON INTERVAL GRAPHS

Cites Work

• Unnamed Item

This page was built for publication: An optimal algorithm to solve the all-pair shortest path problem on interval graphs