Optimal shortest path set problem in undirected graphs

Huili Zhang (), Yinfeng Xu () and Xingang Wen ()
Additional contact information
Huili Zhang: Xi’an Jiaotong University
Yinfeng Xu: Xi’an Jiaotong University
Xingang Wen: Xi’an Jiaotong University

Journal of Combinatorial Optimization, 2015, vol. 29, issue 3, No 1, 530 pages

Abstract: Abstract This paper proposes the optimal shortest path set problem in an undirected graph $$G=(V,E)$$ G = ( V , E ) , in which some vehicles have to go from a source node $$s$$ s to a destination node $$t$$ t . However, at most $$k$$ k edges in the graph may be blocked during the traveling. The goal is to find a minimum collection of paths for the vehicles before they start off to assure the fastest arrival of at least one vehicle, no matter which $$l$$ l $$(0\le l\le k)$$ ( 0 ≤ l ≤ k ) edges are blocked. We consider two scenarios for this problem. In the first scenario with $$k=1$$ k = 1 , we propose the concept of common replacement path and design the Least-Overlap Algorithm to find the common replacement path. Based on this, an algorithm to compute the optimal shortest path set is presented and its time complexity is proved to be $$O(n^2)$$ O ( n 2 ) . In the second scenario with $$k>1$$ k > 1 , we consider the case where the blocked edges are consecutive ones on a shortest path from $$s$$ s to $$t$$ t and the vertices connecting two blocked edges are also blocked (i.e., routes passing through these vertices are not allowed), and an algorithm is presented to compute the optimal shortest path set in this scenario with time complexity $$O(mn+k^2n^2\log n)$$ O ( m n + k 2 n 2 log n ) .

Keywords: Shortest path; Common replacement path; Optimal shortest path set; Time complexity (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-014-9766-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:29:y:2015:i:3:d:10.1007_s10878-014-9766-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-014-9766-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().