Finding a contra-risk path between two nodes in undirected graphs

Mehdi Ghiyasvand () and Iman Keshtkar ()
Additional contact information
Mehdi Ghiyasvand: Bu-Ali Sina University
Iman Keshtkar: Bu-Ali Sina University

Journal of Combinatorial Optimization, 2016, vol. 32, issue 3, No 17, 917-926

Abstract: Abstract Given an undirected graph with a source node s and a sink node t. The anti-risk path problem is defined as the problem of finding a path between node s to node t with the least risk under the assumption that at most one edge of each path may be blocked. Xiao et al. (J Comb Optim 17:235–246, 2009) defined the problem and presented an $$O(mn+n^2 \log n)$$ O ( m n + n 2 log n ) time algorithm to find an anti-risk path, where n and m are the number of nodes and edges, respectively. Recently, Mahadeokar and Saxena (J Comb Optim 27:798–807, 2014) solved the problem in $$O(m+n \log n)$$ O ( m + n log n ) time. In this paper, first, a new version of the anti-risk path (called contra-risk path) is defined, which is more effective than an anti-risk path in many networks. Then, an algorithm to find a contra-risk path is presented, which runs in $$O(m+n \log n)$$ O ( m + n log n ) time.

Keywords: Network flows; The anti-risk path; The shortest path problem (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9912-8 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:32:y:2016:i:3:d:10.1007_s10878-015-9912-8

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

DOI: 10.1007/s10878-015-9912-8

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 ().