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

DOI10.1007/S12190-008-0218-1MaRDI QIDQ1034978zbMATH OpenOpenAlexFDO

Authors Sambhu Charan Barman, Sukumar Mondal, Madhumangal Pal

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 algorithmsnext-to-shortest pathpermutation graphsshortest paths

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) Analysis of algorithms (68W40)

Cites work

• An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs
• Breadth-first traversal of trees and integer sorting in parallel
• Computing strictly-second shortest paths
• Depth-First Search and Linear Graph Algorithms
• Finding next-to-shortest paths in a graph
• Finding the k Shortest Paths
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3446921 (Why is no real title available?)
• Improved algorithm for finding next-to-shortest paths
• Incremental modular decomposition
• The shortest path problem with forbidden paths
• Transitive Orientation of Graphs and Identification of Permutation Graphs

Cited in

(9)

• An efficient algorithm to determine all shortest paths in Sierpiński graphs
• An optimal algorithm to find minimum k-hop dominating set of interval graphs
• A linear algorithms for the two paths problem on permutation graphs
• An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs
• Minimum r-neighborhood covering set of permutation graphs
• Computation of diameter, radius and center of permutation graphs
• An optimal algorithm for computing minimum k-hop dominating set of permutation graphs
• Minimum vertex-edge dominating set of permutation graphs
• L(0,1)-labelling of permutation graphs

This page was built for publication: An efficient algorithm to find next-to-shortest path on permutation graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1034978)