Finding disjoint paths in networks with star shared risk link groups

DOI10.1016/J.TCS.2015.02.012MaRDI QIDQ2344758zbMATH OpenOpenAlexFDO

Authors David Coudert, Gianlorenzo D'Angelo, Fatima Zahra Moataz, Jean-Claude Bermond

Publication date 18 May 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.02.012

zbMATH Keywords

algorithmscolored graphcomplexitydisjoint pathsdiverse routingshared risk link group

Mathematics Subject Classification ID

Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Reliability, availability, maintenance, inspection in operations research (90B25) Programming involving graphs or networks (90C35)

Recommendations

• Combinatorial optimization in networks with shared risk link groups
• SRG-disjoint design with dedicated and shared protection
• scientific article; zbMATH DE number 714464
• Redundant multicast routing in multilayer networks with shared risk resource groups: complexity, models and algorithms
• Graph transformation approaches for diverse routing in shared risk resource group (SRRG) failures

Cites work

• A quick method for finding shortest pairs of disjoint paths
• A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem
• Approximation algorithms and hardness results for labeled connectivity problems
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Disjoint paths in a network
• Finding paths in graphs avoiding forbidden transitions
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Fundamentals of parameterized complexity
• Graph transformation approaches for diverse routing in shared risk resource group (SRRG) failures
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2147947 (Why is no real title available?)
• scientific article; zbMATH DE number 1445322 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• New results on the computability and complexity of points-to analysis
• Set partitioning via inclusion-exclusion
• Structure preserving reductions among convex optimization problems
• The parameterized complexity of some minimum label problems
• Topics in Cryptology – CT-RSA 2004

Cited in

(5)

• Combinatorial optimization in networks with shared risk link groups
• SRG-disjoint design with dedicated and shared protection
• Shared Risk Link Group disjointness and geodiverse routing: A trade‐off between benefit and practical effort
• Bounds of redundant multicast routing problem with SRLG-diverse constraints: edge, path and tree models
• Graph transformation approaches for diverse routing in shared risk resource group (SRRG) failures

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: Finding disjoint paths in networks with star shared risk link groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2344758)