Computational Aspects of Fault Location and Resilience Problems for Interdependent Infrastructure Networks

被引：0
作者：
Marathe, Madhav, V [1 ]
Ravi, S. S. [1 ,2 ]
Rosenkrantz, Daniel J. [2 ]
Stearns, Richard E. [2 ]
机构：
[1] Univ Virginia, Charlottesville, VA 22904 USA
[2] SUNY Albany, Albany, NY 12222 USA
来源：
COMPLEX NETWORKS AND THEIR APPLICATIONS VII, VOL 1 | 2019年 / 812卷
关键词：
FAILURES; MODEL;
D O I：
10.1007/978-3-030-05411-3_70
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
Motivated by applications in diagnosing failures in complex infrastructure networks, we consider the configuration sequence completion problem (CSC) for networked systems. The goal of the CSC problem is to choose values for unknown entries in a specified sequence of configurations of a system so that the resulting sequence represents a valid trajectory of the system. This problem generalizes some known decision problems for dynamical systems. We present efficient algorithms for some versions of the CSC problem and computational intractability results for other versions.
引用
收藏
页码：879 / 890
页数：12
相关论文
共 28 条
  • [1] Amin M., 2002, J INFRASTRUCTURE SYS, V8, P67, DOI DOI 10.1061/(ASCE)1076-0342(2002)8:3(67)
  • [2] Banerjee J, 2017, Arxiv, DOI arXiv:1702.05407
  • [3] Analysing robustness in intra-dependent and inter-dependent networks using a new model of interdependency
    Banerjee, Joydeep
    Basu, Kaustav
    Sen, Arunabha
    [J]. INTERNATIONAL JOURNAL OF CRITICAL INFRASTRUCTURES, 2018, 14 (02) : 156 - 181
  • [4] Barrett C.L., 2004, Society for Industrial and Applied Mathematics News, V37, P1
  • [5] Predecessor existence problems for finite discrete dynamical systems
    Barrett, Chris
    Hunt, Harry B., III
    Marathe, Madhav V.
    Ravi, S. S.
    Rosenkrantz, Daniel J.
    Stearns, Richard E.
    Thakur, Mayur
    [J]. THEORETICAL COMPUTER SCIENCE, 2007, 386 (1-2) : 3 - 37
  • [6] Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems
    Barrett, Chris
    Hunt, Harry B., III
    Marathe, Madhav V.
    Ravi, S. S.
    Rosenkrantz, Daniel J.
    Stearns, Richard E.
    [J]. THEORETICAL COMPUTER SCIENCE, 2011, 412 (30) : 3932 - 3946
  • [7] Bodlaender H., 1997, Proceedings 22nd International Symposium on Mathematical Foundations of Computer Science, MFCS'97, P29
  • [8] Suppressing cascades of load in interdependent networks
    Brummitt, Charles D.
    D'Souza, Raissa M.
    Leicht, E. A.
    [J]. PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2012, 109 (12) : E680 - E689
  • [9] Catastrophic cascade of failures in interdependent networks
    Buldyrev, Sergey V.
    Parshani, Roni
    Paul, Gerald
    Stanley, H. Eugene
    Havlin, Shlomo
    [J]. NATURE, 2010, 464 (7291) : 1025 - 1028
  • [10] Crama Y., 2011, Boolean functions: Theory, algorithms, and applications
123