An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs
From MaRDI portal
Publication:1767365
DOI10.1007/BF02936037zbMath1102.68137MaRDI QIDQ1767365
Anita Saha, Tapan Kumar Pal, Madhumangal Pal
Publication date: 10 March 2005
Published in: Journal of Applied Mathematics and Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02936037
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68W10: Parallel algorithms in computer science
Related Items
A linear time algorithm to compute square of interval graphs and their colouring, \(L(2,1)\)-labeling of interval graphs, A survey of the all-pairs shortest paths problem and its variants in graphs
Uses Software
Cites Work
- A unified approach to parallel depth-first traversals of general trees
- Breadth-first traversal of trees and integer sorting in parallel
- On the exponent of all pairs shortest path problem
- All pairs shortest distances for graphs with small integer length edges
- An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs
- One-dimensional logic gate assignment and interval graphs
- Faster algorithms for the shortest path problem
- An Efficient Test for Circular-Arc Graphs
- Efficient algorithms for interval graphs and circular-arc graphs
- An optimal algorithm to solve the all-pair shortest path problem on interval graphs
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item