IEICE TRANSACTIONS on Fundamentals
Approximation Algorithms for Packing Element-Disjoint Steiner Trees on Bounded Terminal Nodes
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E99-A No.6 pp.1059-1066
- Publication Date
- 2016/06/01
- Publicized
- 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
Authors
Daiki HOSHIKA
Kyushu Institute of Technology
Eiji MIYANO
Kyushu Institute of Technology
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Daiki HOSHIKA, Eiji MIYANO, "Approximation Algorithms for Packing Element-Disjoint Steiner Trees on Bounded Terminal Nodes" in IEICE TRANSACTIONS on Fundamentals,
vol. E99-A, no. 6, pp. 1059-1066, June 2016, doi: 10.1587/transfun.E99.A.1059.
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 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.1059/_p
Copy
@ARTICLE{e99-a_6_1059,
author={Daiki HOSHIKA, Eiji MIYANO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Approximation Algorithms for Packing Element-Disjoint Steiner Trees on Bounded Terminal Nodes},
year={2016},
volume={E99-A},
number={6},
pages={1059-1066},
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 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.},
keywords={},
doi={10.1587/transfun.E99.A.1059},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - Approximation Algorithms for Packing Element-Disjoint Steiner Trees on Bounded Terminal Nodes
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1059
EP - 1066
AU - Daiki HOSHIKA
AU - Eiji MIYANO
PY - 2016
DO - 10.1587/transfun.E99.A.1059
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2016
AB - 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.
ER -
English
