Finding critical regions in a network

Conference paper (2013)
Department
Intelligent Systems (EEMCS) (TU Delft)
Copyright: © 2013 IEEE
More Info
expand_more

Published Date

19-04-2013

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Source:

Proceedings of IEEE INFOCOM 2013, Turin, Italy, 14-19 April 2013; pre-print version, presented at the 5th International NetSciCom

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Intelligent Systems

Abstract

It is important that our vital networks (e.g., infrastructures) are robust to more than single-link failures. Failures might for instance affect a part of the network that resides in a certain geographical region. In this paper, considering networks embedded in a two-dimensional plane, we study the problem of finding a critical region - that is, a part of the network that can be enclosed by a given elementary figure (a circle, ellipse, rectangle, square, or equilateral triangle) with a predetermined size - whose removal would lead to the highest network disruption. We determine that there is a polynomial number of non-trivial positions for such a figure that need to be considered and, subsequently, we propose a polynomial-time algorithm for the problem. Simulations on realistic networks illustrate that different figures with equal area result in different critical regions in a network.