An efficient algorithm to find next-to-shortest path on permutation graphs

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

zbMATH Keywords

analysis of algorithmsdesign of algorithmsshortest pathspermutation graphsnext-to-shortest path

Mathematics Subject Classification ID

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