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

DOI10.1007/BF02936037zbMath1102.68137OpenAlexW2159279760MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (3)

A survey of the all-pairs shortest paths problem and its variants in graphs ⋮ A linear time algorithm to compute square of interval graphs and their colouring ⋮ \(L(2,1)\)-labeling of interval graphs

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs