Improved Approximation Algorithms for Computing k Disjoint Paths Subject to Two Constraints

DOI10.1007/978-3-642-38768-5_30zbMath1381.68306OpenAlexW1487455319MaRDI QIDQ4925249

Hong Shen, Longkun Guo, Kewen Liao

Publication date: 11 June 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-38768-5_30

zbMATH Keywords

NP-hardbifactor approximation algorithmcycle cancellationauxiliary graph\(k\)-disjoint bi-constraint path

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (2)

Efficient approximation algorithms for computing \(k\) disjoint constrained shortest paths ⋮ Redundancy system design for an aircraft door management system

This page was built for publication: Improved Approximation Algorithms for Computing k Disjoint Paths Subject to Two Constraints