WEKO3
アイテム
A ZDD-Based Algorithm for Solving Minimum Weighted Vertex Cover Problems and Its Evaluation
https://ipsj.ixsq.nii.ac.jp/records/220580
https://ipsj.ixsq.nii.ac.jp/records/22058010208b78-740c-4529-a5ab-30479f043d5c
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-Z84-5K-03.pdf (784.5 kB)
|
Copyright (c) 2022 by the Information Processing Society of Japan
|
| Item type | National Convention(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2022-02-17 | |||||||||
| タイトル | ||||||||||
| タイトル | A ZDD-Based Algorithm for Solving Minimum Weighted Vertex Cover Problems and Its Evaluation | |||||||||
| 言語 | ||||||||||
| 言語 | eng | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | ソフトウェア科学・工学 | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||||||
| 資源タイプ | conference paper | |||||||||
| 著者所属 | ||||||||||
| 京大 | ||||||||||
| 著者所属 | ||||||||||
| 京大 | ||||||||||
| 著者名 |
劉, 祥
× 劉, 祥
× 湊, 真一
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | Given an undirected vertex-weighted graph <l>G=（V,E,w）</l>, the minimum weighted vertex cover （MWVC） problem is to find a subset of vertices with every edge in the given graph having at least one of its endpoints selected such that the total weight of the subset is minimum. In this paper, we present a method using the Zero-Suppressed Binary Decision Diagram （ZDD） for solving this classic NP-hard problem, applying an efficient approximation algorithm to facilitate finding the exact solution. We show the experimental evaluation of our method compared with existing solvers including SBMS and Cliquer. | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AN00349328 | |||||||||
| 書誌情報 |
第84回全国大会講演論文集 巻 2022, 号 1, p. 225-226, 発行日 2022-02-17 |
|||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
