TY - GEN

T1 - Geographic max-flow and min-cut under a circular disk failure model

AU - Neumayer, Sebastian

AU - Efrat, Alon

AU - Modiano, Eytan

PY - 2012

Y1 - 2012

N2 - Failures in fiber-optic networks may be caused by natural disasters, such as floods or earthquakes, as well as other events, such as an Electromagnetic Pulse (EMP) attack. These events occur in specific geographical locations, therefore the geography of the network determines the effect of failure events on the network's connectivity and capacity. In this paper we consider a generalization of the min-cut and max-flow problems under a geographic failure model. Specifically, we consider the problem of finding the minimum number of failures, modeled as circular disks, to disconnect a pair of nodes and the maximum number of failure disjoint paths between pairs of nodes. This model applies to the scenario where an adversary is attacking the network multiple times with intention to reduce its connectivity. We present a polynomial time algorithm to solve the geographic min-cut problem and develop an ILP formulation, an exact algorithm, and a heuristic algorithm for the geographic max-flow problem.

AB - Failures in fiber-optic networks may be caused by natural disasters, such as floods or earthquakes, as well as other events, such as an Electromagnetic Pulse (EMP) attack. These events occur in specific geographical locations, therefore the geography of the network determines the effect of failure events on the network's connectivity and capacity. In this paper we consider a generalization of the min-cut and max-flow problems under a geographic failure model. Specifically, we consider the problem of finding the minimum number of failures, modeled as circular disks, to disconnect a pair of nodes and the maximum number of failure disjoint paths between pairs of nodes. This model applies to the scenario where an adversary is attacking the network multiple times with intention to reduce its connectivity. We present a polynomial time algorithm to solve the geographic min-cut problem and develop an ILP formulation, an exact algorithm, and a heuristic algorithm for the geographic max-flow problem.

UR - http://www.scopus.com/inward/record.url?scp=84861610777&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84861610777&partnerID=8YFLogxK

U2 - 10.1109/INFCOM.2012.6195690

DO - 10.1109/INFCOM.2012.6195690

M3 - Conference contribution

AN - SCOPUS:84861610777

SN - 9781467307758

T3 - Proceedings - IEEE INFOCOM

SP - 2736

EP - 2740

BT - 2012 Proceedings IEEE INFOCOM, INFOCOM 2012

T2 - IEEE Conference on Computer Communications, INFOCOM 2012

Y2 - 25 March 2012 through 30 March 2012

ER -