WEKO3
アイテム
最小コスト木状被覆問題の2倍近似アルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/31726
https://ipsj.ixsq.nii.ac.jp/records/3172608abd0b6-5d30-4da1-8ad5-f4796814d071
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 2006 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 2006-07-03 | |||||||
タイトル | ||||||||
タイトル | 最小コスト木状被覆問題の2倍近似アルゴリズム | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | How to trim an MST:A 2-approximation algorithm for minimum cost tree cover | |||||||
言語 | ||||||||
言語 | eng | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
豊橋技術科学大学情報工学系計算機大講座 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of lnformation & Computer Sciences, Toyohashi University of Technology | ||||||||
著者名 |
藤戸, 敏弘
× 藤戸, 敏弘
|
|||||||
著者名(英) |
Toshihiro, Fujito
× Toshihiro, Fujito
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 辺コストをもつ連結グラフGにおいて、その頂点集合がGの頂点被覆を成す木を木状被覆、そのような木の中からコスト最小のものを計算する問題を木状被覆問題という。NP困難である同問題に対し、辺コストが一定の場合、線形時間2倍近似アルゴリズムが従来から知られていたが、任意コストの場合、3倍近似アルゴリズムがベストで、しかもそれらは(多項式時間とはいえ)非効率的である。本稿では、最小スパンニング木の葉を刈ることで、高速な2倍近似アルゴリズムが得られることを示す。 | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | The minimum cost tree cover problem is to compute a minimum cost tree T in a given connected graph G with costs on the edges,such that the vertices of T form a vertex cover for G. The problem is supposed to arise in applications of vertex cover and edge dominating set when connectivity is additionally required in solutions. Whereas a linear-time 2-approximation algorithm for the unweighted case has been known for quite a while, the best approximation ratio known for the weighted case is 3. Moreover, the known 3-approximation algorithm for such case is far from practical in its efficiency. In this paper we present a fast, purely combinatorial 2-approximation algorithm for the minimum cost tree cover problem. It constructs a good approximate solution by trimming some leaves within a minimum spanning tree(MST), and to determine which leaves to trim, it uses both of the primal-dual schema and the local ratio technique in an interlaced fashion. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN1009593X | |||||||
書誌情報 |
情報処理学会研究報告アルゴリズム(AL) 巻 2006, 号 71(2006-AL-107), p. 13-20, 発行日 2006-07-03 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |