Conferences in Research and Practice in Information Technology
  

Online Version - Last Updated - 20 Jan 2012

 

 
Home
 

 
Procedures and Resources for Authors

 
Information and Resources for Volume Editors
 

 
Orders and Subscriptions
 

 
Published Articles

 
Upcoming Volumes
 

 
Contact Us
 

 
Useful External Links
 

 
CRPIT Site Search
 
    

The Next-to-Shortest Path in Undirected Graphs with Nonnegative Weights

Zhang, C. and Nagamochi, H.

    Given an edge-weighted undirected graph and two vertices s and t, the next-to-shortest path problem is to find an st-path whose length is minimum among all st-paths of lengths strictly larger than the shortest path length. The problem is shown to be polynomially solvable if all edge weights are positive, while the complexity status for the nonnegative weight case was open. In this paper we show that the problem in undirected graphs admits a polynomial-time algorithm even if all edge weights are nonnegative, solving the open problem. To solve the problem, we introduce a common generalization of the undirected graph version and the acyclic digraph version of the k vertex-disjoint paths problem.
Cite as: Zhang, C. and Nagamochi, H. (2012). The Next-to-Shortest Path in Undirected Graphs with Nonnegative Weights. In Proc. Computing: The Australasian Theory Symposium (CATS 2012) Melbourne, Australia. CRPIT, 128. Mestre, J. Eds., ACS. 13-20
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS