Title :
Max-flow min-cut theorem and faster algorithms in a circular disk failure model
Author :
Kobayashi, Yoshiyuki ; Otsuki, K.
Author_Institution :
Univ. of Tokyo, Tokyo, Japan
fDate :
April 27 2014-May 2 2014
Abstract :
Fault-tolerance is one of the most important factors in designing networks. Failures in networks are sometimes caused by an event occurring in specific geographical regions such as hurricanes, earthquakes, bomb attacks, and Electromagnetic Pulse (EMP) attacks. In INFOCOM 2012, Neumayer et al. introduced geographical variants of max-flow min-cut problems in a circular disk failure model, in which each failure is represented by a disk with a predetermined size. In this paper, we solve two open problems in this model: we give a first polynomial-time algorithm for the geographic max-flow problem, and prove a conjecture of Neumayer et al. on a relationship between the geographic max-flow and the geographic min-cut.
Keywords :
communication complexity; fault tolerance; minimax techniques; radio networks; telecommunication network planning; telecommunication network reliability; bomb attacks; circular disk failure model; earthquakes; electromagnetic pulse; fault tolerance; geographic max-flow min-cut theorem; geographical region; geographical variant; hurricanes; network design; polynomial-time algorithm; Clocks; Computational modeling; Computers; Conferences; Face; Joining processes; Polynomials;
Conference_Titel :
INFOCOM, 2014 Proceedings IEEE
Conference_Location :
Toronto, ON
DOI :
10.1109/INFOCOM.2014.6848100