WEKO3
アイテム
Approximation Algorithms for Packing Element-Disjoint Steiner Trees on Bounded Terminal Nodes
http://hdl.handle.net/10228/00007448
http://hdl.handle.net/10228/000074483b0959e1-f417-431c-939e-a4fe1cf30218
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
e99-a_6_1059.pdf (1.2 MB)
|
|
| アイテムタイプ | 学術雑誌論文 = Journal Article(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2019-11-25 | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||
| 資源タイプ | journal article | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | Approximation Algorithms for Packing Element-Disjoint Steiner Trees on Bounded Terminal Nodes | |||||||||||||
| 言語 | en | |||||||||||||
| その他のタイトル | ||||||||||||||
| その他のタイトル | Approximation algorithms for packing element-disjoint steiner trees on bounded terminal nodes | |||||||||||||
| 言語 | en | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | eng | |||||||||||||
| 著者 |
Hoshika, Daiki
× Hoshika, Daiki× 宮野, 英次
WEKO
6037
|
|||||||||||||
| 抄録 | ||||||||||||||
| 内容記述タイプ | 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. | |||||||||||||
| 言語 | en | |||||||||||||
| 書誌情報 |
en : IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 巻 E99-A, 号 6, p. 1059-1066, 発行日 2016-06-01 |
|||||||||||||
| 出版社 | ||||||||||||||
| 出版者 | 電子情報通信学会 | |||||||||||||
| 言語 | ja | |||||||||||||
| DOI | ||||||||||||||
| 関連タイプ | isIdenticalTo | |||||||||||||
| 識別子タイプ | DOI | |||||||||||||
| 関連識別子 | https://doi.org/10.1587/transfun.E99.A.1059 | |||||||||||||
| CRID | ||||||||||||||
| 関連タイプ | isIdenticalTo | |||||||||||||
| 識別子タイプ | URI | |||||||||||||
| 関連識別子 | https://cir.nii.ac.jp/crid/1390282681286669056 | |||||||||||||
| 日本十進分類法 | ||||||||||||||
| 主題Scheme | NDC | |||||||||||||
| 主題 | 549 | |||||||||||||
| NCID | ||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||
| 収録物識別子 | AA10826261 | |||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||
| 収録物識別子 | 0916-8516 | |||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | EISSN | |||||||||||||
| 収録物識別子 | 1745-1345 | |||||||||||||
| 著作権関連情報 | ||||||||||||||
| 権利情報 | Copyright (c) 2016 The Institute of Electronics, Information and Communication Engineers | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | element-disjoint Steiner tree packing | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | bounded terminal nodes | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | approximation algorithms | |||||||||||||
| 出版タイプ | ||||||||||||||
| 出版タイプ | VoR | |||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||||
| 査読の有無 | ||||||||||||||
| 値 | yes | |||||||||||||
| 研究者情報 | ||||||||||||||
| URL | https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html | |||||||||||||
| 論文ID（連携） | ||||||||||||||
| 値 | 10347417 | |||||||||||||
| 連携ID | ||||||||||||||
| 値 | 7950 | |||||||||||||
