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.
Publication Year: 2007
Publication Date: 2007-11-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 32
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot