On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints

DOI10.1006/jcss.1999.1661zbMath0952.68002OpenAlexW1966838648MaRDI QIDQ1975964

Lusheng Wang, Bin Ma

Publication date: 8 May 2000

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1999.1661

zbMATH Keywords

network optimization

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Mathematical problems of computer architecture (68M07) Computer system organization (68M99)

Related Items (8)

Minimum \(k\) arborescences with bandwidth constraints ⋮ On the disjoint paths problem ⋮ On the edge capacitated Steiner tree problem ⋮ On routing in VLSI design and communication networks ⋮ Finding edge-disjoint paths in networks: an ant colony optimization algorithm ⋮ Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems ⋮ Packing trees in communication networks ⋮ Fixed topology Steiner trees and spanning forests

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the Computational Complexity of Combinatorial Problems
• Improved Approximation Algorithms for Shop Scheduling Problems
• Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

This page was built for publication: On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints