Combinatorial optimization in networks with Shared Risk Link Groups
The notion of Shared Risk Link Groups (SRLG) captures survivability issues when a set of links of a network may fail simultaneously. The theory of survivable network design relies on basic combinatorial objects that are rather easy to compute in the classical graph models: shortest paths, minimum cu...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2016-05-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/1297/pdf |
| _version_ | 1797270057204580352 |
|---|---|
| author | David Coudert Stéphane Pérennes Hervé Rivano Marie-Emilie Voge |
| author_facet | David Coudert Stéphane Pérennes Hervé Rivano Marie-Emilie Voge |
| author_sort | David Coudert |
| collection | DOAJ |
| description | The notion of Shared Risk Link Groups (SRLG) captures survivability issues when a set of links of a network may fail simultaneously. The theory of survivable network design relies on basic combinatorial objects that are rather easy to compute in the classical graph models: shortest paths, minimum cuts, or pairs of disjoint paths. In the SRLG context, the optimization criterion for these objects is no longer the number of edges they use, but the number of SRLGs involved. Unfortunately, computing these combinatorial objects is NP-hard and hard to approximate with this objective in general. Nevertheless some objects can be computed in polynomial time when the SRLGs satisfy certain structural properties of locality which correspond to practical ones, namely the star property (all links affected by a given SRLG are incident to a unique node) and the span 1 property (the links affected by a given SRLG form a connected component of the network). The star property is defined in a multi-colored model where a link can be affected by several SRLGs while the span property is defined only in a mono-colored model where a link can be affected by at most one SRLG. In this paper, we extend these notions to characterize new cases in which these optimization problems can be solved in polynomial time. We also investigate the computational impact of the transformation from the multi-colored model to the mono-colored one. Experimental results are presented to validate the proposed algorithms and principles. |
| first_indexed | 2024-04-25T01:58:13Z |
| format | Article |
| id | doaj.art-1ce3f4a6a91444cfa9541f4485aaf64d |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:13Z |
| publishDate | 2016-05-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-1ce3f4a6a91444cfa9541f4485aaf64d2024-03-07T15:31:26ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502016-05-01Vol. 18 no. 3Distributed Computing and...10.46298/dmtcs.12971297Combinatorial optimization in networks with Shared Risk Link GroupsDavid Coudert0https://orcid.org/0000-0002-3306-8314Stéphane Pérennes1Hervé Rivano2https://orcid.org/0000-0001-6112-7468Marie-Emilie Voge3https://orcid.org/0000-0002-1361-9094Combinatorics, Optimization and Algorithms for TelecommunicationsCombinatorics, Optimization and Algorithms for TelecommunicationsRéseaux capillaires urbainsLaboratoire d'Informatique Fondamentale de LilleThe notion of Shared Risk Link Groups (SRLG) captures survivability issues when a set of links of a network may fail simultaneously. The theory of survivable network design relies on basic combinatorial objects that are rather easy to compute in the classical graph models: shortest paths, minimum cuts, or pairs of disjoint paths. In the SRLG context, the optimization criterion for these objects is no longer the number of edges they use, but the number of SRLGs involved. Unfortunately, computing these combinatorial objects is NP-hard and hard to approximate with this objective in general. Nevertheless some objects can be computed in polynomial time when the SRLGs satisfy certain structural properties of locality which correspond to practical ones, namely the star property (all links affected by a given SRLG are incident to a unique node) and the span 1 property (the links affected by a given SRLG form a connected component of the network). The star property is defined in a multi-colored model where a link can be affected by several SRLGs while the span property is defined only in a mono-colored model where a link can be affected by at most one SRLG. In this paper, we extend these notions to characterize new cases in which these optimization problems can be solved in polynomial time. We also investigate the computational impact of the transformation from the multi-colored model to the mono-colored one. Experimental results are presented to validate the proposed algorithms and principles.https://dmtcs.episciences.org/1297/pdfcolored graphsshared risk link groupcomplexityalgorithmsmulti-layer networks[info.info-ni] computer science [cs]/networking and internet architecture [cs.ni] |
| spellingShingle | David Coudert Stéphane Pérennes Hervé Rivano Marie-Emilie Voge Combinatorial optimization in networks with Shared Risk Link Groups Discrete Mathematics & Theoretical Computer Science colored graphs shared risk link group complexity algorithms multi-layer networks [info.info-ni] computer science [cs]/networking and internet architecture [cs.ni] |
| title | Combinatorial optimization in networks with Shared Risk Link Groups |
| title_full | Combinatorial optimization in networks with Shared Risk Link Groups |
| title_fullStr | Combinatorial optimization in networks with Shared Risk Link Groups |
| title_full_unstemmed | Combinatorial optimization in networks with Shared Risk Link Groups |
| title_short | Combinatorial optimization in networks with Shared Risk Link Groups |
| title_sort | combinatorial optimization in networks with shared risk link groups |
| topic | colored graphs shared risk link group complexity algorithms multi-layer networks [info.info-ni] computer science [cs]/networking and internet architecture [cs.ni] |
| url | https://dmtcs.episciences.org/1297/pdf |
| work_keys_str_mv | AT davidcoudert combinatorialoptimizationinnetworkswithsharedrisklinkgroups AT stephaneperennes combinatorialoptimizationinnetworkswithsharedrisklinkgroups AT herverivano combinatorialoptimizationinnetworkswithsharedrisklinkgroups AT marieemilievoge combinatorialoptimizationinnetworkswithsharedrisklinkgroups |