Packing element-disjoint steiner trees
Authors:
Open Access
- 1 November 2007
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 3 (4) , 47
Abstract
Given an undirected graph G ( V , E ) with terminal set T ⊆ V , the problem of packing element-disjoint Steiner trees is to find the maximum number of Steiner trees that are disjoint on the nonterminal nodes and on the edges. The problem is known to be NP-hard to approximate within a factor of Ω(log n ), where n denotes | V |. We present a randomized O (log n )-approximation algorithm for this problem, thus matching the hardness lower bound. Moreover, we show a tight upper bound of O (log n ) on the integrality ratio of a natural linear programming relaxation.Keywords
This publication has 16 references indexed in Scilit:
- Hardness and approximation results for packing steiner treesAlgorithmica, 2006
- Multicast time maximization in energy constrained wireless networks2003
- Highly connected hypergraphs containing no two edge-disjoint spanning connected subhypergraphsDiscrete Applied Mathematics, 2003
- On decomposing a hypergraph into k connected sub-hypergraphsDiscrete Applied Mathematics, 2003
- Randomized metaroundingRandom Structures & Algorithms, 2002
- Approximating theDomatic NumberSIAM Journal on Computing, 2002
- Packing Steiner Trees: Separation AlgorithmsSIAM Journal on Discrete Mathematics, 1996
- Packing Steiner trees: a cutting plane algorithm and computational resultsMathematical Programming, 1996
- Packing Steiner trees: polyhedral investigationsMathematical Programming, 1996
- Packing Steiner Trees: Further FacetsEuropean Journal of Combinatorics, 1996