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
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
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