An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
From MaRDI portal
Recommendations
- Parallel implementation of shortest paths problem on weighted interval and circular arc graphs
- Solving the all-pair shortest path query problem on interval and circular-arc graphs
- Optimal parallel algorithm for shortest-paths problem on interval graphs
- An optimal algorithm to solve the all-pair shortest path problem on interval graphs
- Linear time algorithms on circular-arc graphs
Cites work
- A class of algorithms which require nonlinear time to maintain disjoint sets
- A linear-time algorithm for a special case of disjoint set union
- An optimal algorithm to solve the all-pair shortest path problem on interval graphs
- An optimal parallel algorithm for the minimum circle-cover problem
- Efficient algorithms for interval graphs and circular-arc graphs
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- On a circle-cover minimization problem
- Parallel circle-cover algorithms
- Preserving order in a forest in less than logarithmic time and linear space
- RESTRICTED TRACK ASSIGNMENT WITH APPLICATIONS
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
Cited in
(23)- Localized and compact data-structure for comparability graphs
- Optimal parallel algorithms on circular-arc graphs
- Unified all-pairs shortest path algorithms in the chordal hierarchy
- A new algorithm for reoptimizing shortest paths when the arc costs change
- All-pairs-shortest-length on strongly chordal graphs
- Disconnected cuts in claw-free graphs
- Near-optimal algorithms for shortest paths in weighted unit-disk graphs
- Shortest-path-preserving rounding
- Algorithms for interval structures with applications
- Distance Labeling for Permutation Graphs
- Parallel implementation of shortest paths problem on weighted interval and circular arc graphs
- Algorithms for interval structures with applications
- Optimally fast shortest path algorithms for some classes of graphs
- Solving the all-pair shortest path query problem on interval and circular-arc graphs
- Skeletons, recognition algorithm and distance matrix of quasi-median graphs
- Computing and Combinatorics
- Impact of soft ride time constraints on the complexity of scheduling in dial-a-ride problems
- Intersection graphs of non-crossing paths
- Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh
- Revised eight-step feasibility checking procedure with linear time complexity for the dial-a-ride problem (DARP)
- On paths with the shortest average arc length in weighted graphs
- The subinterval cover problem
- Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms
This page was built for publication: An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1900895)
