Improved max-flow min-cut algorithms in a Circular Disk Failure Model with application to a road network

Kensuke Otsuki, Yusuke Kobayashi and Kazuo Murota

European Journal of Operational Research, 2016, vol. 248, issue 2, 396-403

Abstract: In the evaluation of network reliability, the objectives are to model reliability of networks appropriately and to compute it in a realistic time. We can consider various models of reliability of networks, and Bienstock (1991) first introduced a geographical failure model where each failure is represented by a 2-dimensional region. In this model, we consider the situation that geographical networks such as road networks may be damaged by externally caused disasters, and such disasters may destroy several links of the networks simultaneously, rather than each link independently. Recently, Neumayer–Efrat–Modiano (2012) investigated the max-flow problem and the min-cut problem under the Circular Disk Failure Model, in which the shape of each failure is restricted to be a disk. Under this model, Kobayashi–Otsuki (2014) gave polynomial time algorithms to find optimal solutions of these two problems. In this paper, we improve the algorithms and evaluate their performance by computational experiments. Although our improvements work only when the max-flow value is equal to the min-cut value, this condition holds in almost all practical cases. Owing to the improvements, we can find in a realistic time optimal solutions of the max-flow problem and the min-cut problem in large networks under the Circular Disk Failure Model. As a realistic instance, we analyze reliability of a road network in NewYork consisting of 264,346 nodes.

Keywords: Combinatorial optimization; Networks; Reliability; Graph theory (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221715006694
Full text for ScienceDirect subscribers only

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:eee:ejores:v:248:y:2016:i:2:p:396-403

DOI: 10.1016/j.ejor.2015.07.035

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().