WEKO3
アイテム
最大次数3の平面的グラフにおける事前割当による最小頂点被覆の唯一化の計算困難性
https://ipsj.ixsq.nii.ac.jp/records/241899
https://ipsj.ixsq.nii.ac.jp/records/24189927e3f363-3487-459a-8c64-2122ed958c3b
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL25201011.pdf (1.2 MB)
2027年1月7日からダウンロード可能です。
|
Copyright (c) 2025 by the Information Processing Society of Japan
|
|
| 非会員：¥660, IPSJ:学会員：¥330, AL:会員：¥0, DLIB:会員：¥0 | ||
| Item type | SIG Technical Reports(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2025-01-07 | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | 最大次数3の平面的グラフにおける事前割当による最小頂点被覆の唯一化の計算困難性 | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | jpn | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||||||
| 資源タイプ | technical report | |||||||||||||
| 著者所属 | ||||||||||||||
| 北海道大学 | ||||||||||||||
| 著者所属 | ||||||||||||||
| 北海道大学 | ||||||||||||||
| 著者所属 | ||||||||||||||
| 北海道大学 | ||||||||||||||
| 著者所属 | ||||||||||||||
| 北海道大学 | ||||||||||||||
| 著者所属(英) | ||||||||||||||
| en | ||||||||||||||
| Hokkaido University | ||||||||||||||
| 著者所属(英) | ||||||||||||||
| en | ||||||||||||||
| Hokkaido University | ||||||||||||||
| 著者所属(英) | ||||||||||||||
| en | ||||||||||||||
| Hokkaido University | ||||||||||||||
| 著者所属(英) | ||||||||||||||
| en | ||||||||||||||
| Hokkaido University | ||||||||||||||
| 著者名 |
坂本, 郁弥
× 坂本, 郁弥
× 鈴木, 琉
× 脊戸, 和寿
× 堀山, 貴史
|
|||||||||||||
| 論文抄録 | ||||||||||||||
| 内容記述タイプ | Other | |||||||||||||
| 内容記述 | 与えられた n 頂点のグラフ G のうち，特定の頂点を頂点被覆に含める/含めないを選ぶことを事前割当という．事前割当を満たす G 上の最小頂点被覆が唯一となるような，k 頂点の事前割当が存在するかどうかを判定する問題を PAU-VC (Pre-Assginment for Uniquigying minimum Vertex Cover）という．Horiyama らは，PAU-VC が一般グラフ上で Σp2 完全となることを示し，2 部グラフ上では NP 完全となることを示した．本研究では，最大次数が 3 の平面的グラフに限ったとしても，PAU-VC が Σp2 完全であることを示す． | |||||||||||||
| 書誌レコードID | ||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||
| 収録物識別子 | AN1009593X | |||||||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2025-AL-201, 号 11, p. 1-8, 発行日 2025-01-07 |
|||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||||
| 収録物識別子 | 2188-8566 | |||||||||||||
| Notice | ||||||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||||||
| 出版者 | ||||||||||||||
| 言語 | ja | |||||||||||||
| 出版者 | 情報処理学会 | |||||||||||||
