WEKO3
アイテム
順列グラフのカラフル独立集合問題に対するアルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/210284
https://ipsj.ixsq.nii.ac.jp/records/210284f67d0094-afb8-4356-9ab9-f42cd04f3717
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL21182003.pdf (778.8 kB)
|
Copyright (c) 2021 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2021-03-10 | |||||||||||
| タイトル | ||||||||||||
| タイトル | 順列グラフのカラフル独立集合問題に対するアルゴリズム | |||||||||||
| 言語 | ||||||||||||
| 言語 | jpn | |||||||||||
| 資源タイプ | ||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||||
| 資源タイプ | technical report | |||||||||||
| 著者所属 | ||||||||||||
| 京都大学 | ||||||||||||
| 著者所属 | ||||||||||||
| 京都大学 | ||||||||||||
| 著者所属 | ||||||||||||
| 京都大学 | ||||||||||||
| 著者名 |
吉村, 仁志
× 吉村, 仁志
× 小林, 靖明
× 山本, 章博
|
|||||||||||
| 論文抄録 | ||||||||||||
| 内容記述タイプ | Other | |||||||||||
| 内容記述 | グラフのカラフル独立集合問題は，頂点に色がついたグラフが与えられ，頂点集合の部分集合で独立かつカラフル，つまり部分集合内の任意の頂点が互いに隣接せずかつ色が相異なるもので最大の要素数のものを見つける問題である．この問題は，通常の最大独立集合問題の一般化であり，与えられたグラフが特定のグラフクラスに属する場合でも興味深い分析が行われている．本研究では，与えられたグラフが順列グラフの場合を考え，この問題の固定パラメータアルゴリズムや指数時間厳密アルゴリズムを議論する． | |||||||||||
| 書誌レコードID | ||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||
| 収録物識別子 | AN1009593X | |||||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2021-AL-182, 号 3, p. 1-6, 発行日 2021-03-10 |
|||||||||||
| ISSN | ||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||
| 収録物識別子 | 2188-8566 | |||||||||||
| Notice | ||||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||||
| 出版者 | ||||||||||||
| 言語 | ja | |||||||||||
| 出版者 | 情報処理学会 | |||||||||||
