An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs

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

Mathematics Subject Classification ID

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

• Algorithm 97

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