caa a22 4500 445805463 CHVBK 20180317145155.0 cr unu---uuuuu 170323e20111001xx s 000 0 eng 10.1007/s00453-010-9402-4 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9402-4 A Quadratic Algorithm for Finding Next-to-Shortest Paths in Graphs [Elektronische Daten] [Kuo-Hua Kao, Jou-Ming Chang, Yue-Li Wang, Justie Juan] Given an edge-weighted undirected graph G and two prescribed vertices u and v, a next-to-shortest (u,v)-path is a shortest (u,v)-path amongst all (u,v)-paths having length strictly greater than the length of a shortest (u,v)-path. In this paper, we deal with the problem of computing a next-to-shortest (u,v)-path. We propose an ${\mathcal{O}}(n^{2})$ time algorithm for solving this problem, which significantly improves the bound of a previous one in ${\mathcal{O}}(n^{3})$ time where n is the number of vertices inG. Springer Science+Business Media, LLC, 2010 Strictly-second-shortest paths nationallicence Next-to-shortest paths nationallicence Graph algorithms nationallicence Kao Kuo-Hua Department of Computer Science and Information Engineering, National Chi Nan University, Nantou, Taiwan, ROC aut Chang Jou-Ming Institute of Information Science and Management, National Taipei College of Business, Taipei, Taiwan, ROC aut Wang Yue-Li Department of Information Management, National Taiwan University of Science and Technology, Taipei, Taiwan, ROC aut Juan Justie Department of Computer Science and Information Engineering, National Chi Nan University, Nantou, Taiwan, ROC aut Algorithmica Springer-Verlag 61/2(2011-10-01), 402-418 0178-4617 61:2<402 2011 61 453 https://doi.org/10.1007/s00453-010-9402-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9402-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Kao Kuo-Hua Department of Computer Science and Information Engineering, National Chi Nan University, Nantou, Taiwan, ROC aut NATIONALLICENCE 700 1- Chang Jou-Ming Institute of Information Science and Management, National Taipei College of Business, Taipei, Taiwan, ROC aut NATIONALLICENCE 700 1- Wang Yue-Li Department of Information Management, National Taiwan University of Science and Technology, Taipei, Taiwan, ROC aut NATIONALLICENCE 700 1- Juan Justie Department of Computer Science and Information Engineering, National Chi Nan University, Nantou, Taiwan, ROC aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/2(2011-10-01), 402-418 0178-4617 61:2<402 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer