Finding disjoint paths in networks with star shared risk link groups

DOI10.1016/j.tcs.2015.02.012zbMath1311.90015OpenAlexW2089079148MaRDI QIDQ2344758

David Coudert, Fatima Zahra Moataz, Gianlorenzo D'Angelo, 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

complexityalgorithmscolored graphdisjoint pathsdiverse routingshared risk link group

Mathematics Subject Classification ID

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

Uses Software

• Algorithm 447

Cites Work

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