An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications

DOI10.1007/BF01192049zbMath0830.68051OpenAlexW2763025185MaRDI QIDQ1900895

Danny Z. Chen, Mikhail J. Atallah, Der-Tsai Lee

Publication date: 4 February 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01192049

zbMATH Keywords

shortest pathsinterval graphscircular-arc graphcircle-cover problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (14)

Unified all-pairs shortest path algorithms in the chordal hierarchy ⋮ Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms ⋮ All-pairs-shortest-length on strongly chordal graphs ⋮ Algorithms for interval structures with applications ⋮ Skeletons, recognition algorithm and distance matrix of quasi-median graphs ⋮ Disconnected cuts in claw-free graphs ⋮ Impact of soft ride time constraints on the complexity of scheduling in dial-a-ride problems ⋮ Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh ⋮ Algorithms for Interval Structures with Applications ⋮ Intersection graphs of non-crossing paths ⋮ Optimal parallel algorithms on circular-arc graphs ⋮ Localized and compact data-structure for comparability graphs ⋮ Distance Labeling for Permutation Graphs ⋮ Optimally fast shortest path algorithms for some classes of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• A class of algorithms which require nonlinear time to maintain disjoint sets
• On a circle-cover minimization problem
• A linear-time algorithm for a special case of disjoint set union
• Parallel circle-cover algorithms
• An optimal parallel algorithm for the minimum circle-cover problem
• Preserving order in a forest in less than logarithmic time and linear space
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Efficient algorithms for interval graphs and circular-arc graphs
• An optimal algorithm to solve the all-pair shortest path problem on interval graphs
• RESTRICTED TRACK ASSIGNMENT WITH APPLICATIONS

This page was built for publication: An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications