WEKO3
アイテム
d-claw freeグラフの重み付き最大独立集合問題に対するタブーサーチ法の提案
https://ipsj.ixsq.nii.ac.jp/records/31630
https://ipsj.ixsq.nii.ac.jp/records/316305cf55ca0-1add-4ad4-a68d-1957a62f8e12
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL08116001.pdf (545.5 kB)
|
Copyright (c) 2008 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2008-01-23 | |||||||
| タイトル | ||||||||
| タイトル | d-claw freeグラフの重み付き最大独立集合問題に対するタブーサーチ法の提案 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | A tabu search approach for the maximum weighted independent set problem on d-claw free graphs | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 群馬大学工学部情報工学科 | ||||||||
| 著者所属 | ||||||||
| 群馬大学工学部情報工学科 | ||||||||
| 著者所属 | ||||||||
| 群馬大学工学部情報工学科 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science Gunma University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science Gunma University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science Gunma University | ||||||||
| 著者名 |
青木, 一正
× 青木, 一正
|
|||||||
| 著者名(英) |
Kazumasa, AOKI
× Kazumasa, AOKI
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | d-clawとは，完全2部グラフK1 dと同型な誘導部分グラフである．d-claw freeグラフとは，d-clawを持たないグラフである．d-claw freeグラフに対する重み付き最大独立集合問題に対しては，いくつかの近似アルゴリズムが提案されている．良い近似率を保証するアルゴリズムは，dが小さく，かつ頂点数が少ないグラフに対しては，良い解を得られる[14]．本論文では，Bermanと Krysta [3]のOptimizing Misdirectionを基としたタブーサーチ法を提案し，より良い解が得られることを実験的に示す．比較のために，Pullan 等[17 15 16]が提案した（一般のグラフにおける）重み付き最大クリーク問題に対するメタヒューリスティックアルゴリズムを実装し，実験を行った． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | A d-claw is an induced subgraph isomorphic to K1,d. A graph is d-claw free if it has no d-claw. Several approximation algorithms for the maximum weighted independent set problem on d-claw free graphs have been proposed. In this paper, we propose a new tabu search algorithm based on Berman and Krysta's “Optimizing Misdirection”[3]. And we demonstrate experimentally that our tabu search works well for sparse d-claw free graphs generated in natural ways. To evaluate the performance, we compare our tabu search with a heuristic algorithm introduced by Pullan and Hoos [17,15,16] which works for any weighted graph. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 2008, 号 6(2008-AL-116), p. 1-8, 発行日 2008-01-23 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
