Detecting resilient structures in stochastic networks: A two‐stage stochastic optimization approach
| Autor: | Maciej Rysz, Pavlo A. Krokhmal, Eduardo L. Pasiliao |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Mathematical optimization
021103 operations research Computer Networks and Communications Subgraph isomorphism problem 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology 01 natural sciences Stochastic programming Graph Maximum common subgraph isomorphism problem Clique problem 010201 computation theory & mathematics Hardware and Architecture Stochastic optimization Induced subgraph isomorphism problem Software Budget constraint MathematicsofComputing_DISCRETEMATHEMATICS Information Systems Mathematics |
| Zdroj: | Networks. 69:189-204 |
| ISSN: | 1097-0037 0028-3045 |
| DOI: | 10.1002/net.21727 |
| Popis: | We propose a two-stage stochastic programming framework for designing or identifying “resilient,” or “reparable” structures in graphs whose topology may undergo a stochastic transformation. The reparability of a subgraph satisfying a given property is defined in terms of a budget constraint, which allows for a prescribed number of vertices to be added to or removed from the subgraph so as to restore its structural properties after the observation of random changes to the graph's set of edges. A two-stage stochastic programming model is formulated and is shown to be N P -complete for a broad range of graph-theoretical properties that the resilient subgraph is required to satisfy. A general combinatorial branch-and-bound algorithm is developed, and its computational performance is illustrated on the example of a two-stage stochastic maximum clique problem. © 2016 Wiley Periodicals, Inc. NETWORKS, 2016 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text