Approximation Algorithms for Packing Element-Disjoint Steiner Trees on Bounded Terminal Nodes

Daiki HOSHIKA  Eiji MIYANO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A   No.6   pp.1059-1066
Publication Date: 2016/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.1059
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
element-disjoint Steiner tree packing,  bounded terminal nodes,  approximation algorithms,  

Full Text: PDF(756.5KB)>>
Buy this Article



Summary: 
In this paper we discuss approximation algorithms for the ELEMENT-DISJOINT STEINER TREE PACKING problem (Element-STP for short). For a graph G=(V,E) and a subset of nodes T⊆V, called terminal nodes, a Steiner tree is a connected, acyclic subgraph that contains all the terminal nodes in T. The goal of Element-STP is to find as many element-disjoint Steiner trees as possible. Element-STP is known to be APX-hard even for |T|=3 [1]. It is also known that Element-STP is NP-hard to approximate within a factor of Ω(log |V|) [3] and there is an O(log |V|)-approximation algorithm for Element-STP [2],[4]. In this paper, we provide a $lceil rac{|T|}{2} ceil$-approximation algorithm for Element-STP on graphs with |T| terminal nodes. Furthermore, we show that the approximation ratio of 3 for Element-STP on graphs with five terminal nodes can be improved to 2.