A quadratic algorithm for finding next-to-shortest paths in graphs

DOI10.1007/s00453-010-9402-4zbMath1250.05108OpenAlexW2154828731MaRDI QIDQ639280

Jou-Ming Chang, Justie Su-Tzu Juan, Yue-Li Wang, Kuo-Hua Kao

Publication date: 20 September 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9402-4

zbMATH Keywords

algorithmedge weighted graphnext-to-shortest path

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Simple paths with exact and forbidden lengths ⋮ Approximating the Canadian traveller problem with online randomization ⋮ A simpler and more efficient algorithm for the next-to-shortest path problem ⋮ An efficient algorithm to construct disjoint path covers of DCell networks

Cites Work

• Unnamed Item
• A note on two problems in connexion with graphs
• Computing strictly-second shortest paths
• Finding next-to-shortest paths in a graph
• Improved algorithm for finding next-to-shortest paths
• Finding Dominators in Directed Graphs

This page was built for publication: A quadratic algorithm for finding next-to-shortest paths in graphs