Solving the all-pair shortest path query problem on interval and circular-arc graphs

DOI10.1002/(SICI)1097-0037(199807)31:4%3C249::AID-NET5%3E3.0.CO;2-DMaRDI QIDQ4540051zbMATH OpenOpenAlexFDO

Authors

Publication date 21 July 2002

Full work available at URL https://doi.org/10.1002/(sici)1097-0037(199807)31:4%3C249::aid-net5%3E3.0.co;2-d

zbMATH Keywords

all-pair shortest path query problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Recommendations

• An optimal algorithm to solve the all-pair shortest path problem on interval graphs
• An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs
• scientific article; zbMATH DE number 913360
• An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
• O(1) QUERY TIME ALGORITHM FOR ALL PAIRS SHORTEST DISTANCES ON INTERVAL GRAPHS
• A survey of the all-pairs shortest paths problem and its variants in graphs
• All-pairs shortest paths in geometric intersection graphs
• All-pairs shortest paths in geometric intersection graphs
• Solving all-pairs shortest path by single-source computations: theory and practice
• Solving the all-pairs-shortest-length problem on chordal bipartite graphs

Cited in

(23)

• Efficient algorithms for centers and medians in interval and circular-arc graphs
• Localized and compact data-structure for comparability graphs
• Disconnected cuts in claw-free graphs
• Disconnected cuts in claw-free graphs
• Solving the path cover problem on circular-arc graphs by using an approximation algorithm
• The \(p\)-Maxian problem on interval graphs
• Backup 2-center on interval graphs
• Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs
• Distance queries over dynamic interval graphs
• Deferred-query—An efficient approach for problems on interval and circular-arc graphs
• Algorithms for interval structures with applications
• O(1) QUERY TIME ALGORITHM FOR ALL PAIRS SHORTEST DISTANCES ON INTERVAL GRAPHS
• An improved algorithm for the p-center problem on interval graphs with unit lengths
• An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
• An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
• scientific article; zbMATH DE number 913360 (Why is no real title available?)
• \(O(1)\) query time algorithm for all pairs shortest distances on permutation graphs
• Parallel implementation of shortest paths problem on weighted interval and circular arc graphs
• Succinct encodings for families of interval graphs
• Distance Labeling for Permutation Graphs
• Parameterized complexity of diameter
• Algorithms for interval structures with applications
• Unified all-pairs shortest path algorithms in the chordal hierarchy

This page was built for publication: Solving the all-pair shortest path query problem on interval and circular-arc graphs

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