On the Inapproximability of Disjoint Paths and Minimum Steiner Forest with Bandwidth Constraints
- 1 February 2000
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 60 (1) , 1-12
- https://doi.org/10.1006/jcss.1999.1661
Abstract
No abstract availableKeywords
This publication has 10 references indexed in Scilit:
- Throughput-competitive on-line routingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Short paths in expander graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Disjoint paths in densely embedded graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problemsPublished by Association for Computing Machinery (ACM) ,1999
- Approximating Disjoint-Path Problems Using Greedy Algorithms and Packing Integer ProgramsPublished by Springer Nature ,1998
- A group multicast routing algorithm by using multiple minimum Steiner treesComputer Communications, 1997
- Approximations for the disjoint paths problem in high-diameter planar networksPublished by Association for Computing Machinery (ACM) ,1995
- Improved Approximation Algorithms for Shop Scheduling ProblemsSIAM Journal on Computing, 1994
- On the Computational Complexity of Combinatorial ProblemsNetworks, 1975