An efficient algorithm to find next-to-shortest path on permutation graphs
From MaRDI portal
Publication:1034978
DOI10.1007/s12190-008-0218-1zbMath1194.68267OpenAlexW2116091862MaRDI QIDQ1034978
Madhumangal Pal, Sambhu Charan Barman, Sukumar Mondal
Publication date: 9 November 2009
Published in: Journal of Applied Mathematics and Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s12190-008-0218-1
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)
Related Items (5)
\(L(0,1)\)-labelling of permutation graphs ⋮ Computation of diameter, radius and center of permutation graphs ⋮ An optimal algorithm to find minimum k-hop dominating set of interval graphs ⋮ An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs ⋮ Minimum r-neighborhood covering set of permutation graphs
Cites Work
- Unnamed Item
- Unnamed Item
- The shortest path problem with forbidden paths
- Computing strictly-second shortest paths
- Finding next-to-shortest paths in a graph
- Improved algorithm for finding next-to-shortest paths
- Breadth-first traversal of trees and integer sorting in parallel
- An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs
- Incremental modular decomposition
- Finding the k Shortest Paths
- Transitive Orientation of Graphs and Identification of Permutation Graphs
- Depth-First Search and Linear Graph Algorithms
This page was built for publication: An efficient algorithm to find next-to-shortest path on permutation graphs