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

• HOSHIKA Daiki

  Department of Systems Design and Informatics, Kyushu Institute of Technology

• MIYANO Eiji

  Department of Systems Design and Informatics, Kyushu Institute of Technology

Abstract

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 \frac{|T|}{2}\rceil$-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.

Journal

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E99.A (6), 1059-1066, 2016

  The Institute of Electronics, Information and Communication Engineers

Keywords

• element-disjoint Steiner tree packing
• bounded terminal nodes
• approximation algorithms

Details

• CRID: 1390282681286669056
• NII Article ID: 130005154227
• NII Book ID: AA10826261
• DOI: 10.1587/transfun.e99.a.1059
• ISSN: 17451337
• ISSN: 17451345
• ISSN: 09168508
• ISSN: 09168516
• HANDLE: 10228/00007448
• Web Site: https://kyutech.repo.nii.ac.jp/records/6238
• Web Site: https://www.jstage.jst.go.jp/article/transfun/E99.A/6/E99.A_1059/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • IRDB
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed