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 algorithmsshortest pathsdesign of algorithmspermutation graphsnext-to-shortest path

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3446921 (Why is no real title available?)
• 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
• 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

(7)

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