WEKO3
アイテム
辺カット型グラフパラメータに基づく最大出次数最小化問題と標的集合選択問題の計算複雑性
https://ipsj.ixsq.nii.ac.jp/records/238532
https://ipsj.ixsq.nii.ac.jp/records/238532c5c94d4d-724b-4277-bf86-ee625cd84e64
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL24199005.pdf (1.1 MB)
2026年8月29日からダウンロード可能です。
|
Copyright (c) 2024 by the Information Processing Society of Japan
|
|
| 非会員：¥660, IPSJ:学会員：¥330, AL:会員：¥0, DLIB:会員：¥0 | ||
| Item type | SIG Technical Reports(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2024-08-29 | |||||||||||
| タイトル | ||||||||||||
| タイトル | 辺カット型グラフパラメータに基づく最大出次数最小化問題と標的集合選択問題の計算複雑性 | |||||||||||
| 言語 | ||||||||||||
| 言語 | jpn | |||||||||||
| 資源タイプ | ||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||||
| 資源タイプ | technical report | |||||||||||
| 著者所属 | ||||||||||||
| 北海道大学 | ||||||||||||
| 著者所属 | ||||||||||||
| 北海道大学 | ||||||||||||
| 著者所属 | ||||||||||||
| 北海道大学 | ||||||||||||
| 著者名 |
藤原, 優
× 藤原, 優
× 儀間, 達也
× 小林, 靖明
|
|||||||||||
| 論文抄録 | ||||||||||||
| 内容記述タイプ | Other | |||||||||||
| 内容記述 | グラフの最大出次数最小化問題と標的集合選択問題に関して，グラフの構造的パラメータの視点での固定パラメータ容易性について議論する．これらの問題は，グラフの構造的パラメータを用いたパラメータ化計算量の研究がよく行われているが，非常に限定された範囲でも困難であることがわかっている．本稿では，Ganian と Korchemna (Algorithmica 2024) によって導入されたスリム木カット幅と呼ばれる辺カットに基づくグラフの構造的パラメータを用いて，前述の 2 つの問題のパラメータ化計算量を議論する．具体的には，どちらの問題もスリム木カット幅をパラメータとして固定パラメータ容易であることを示す．さらに，最大出次数最小化問題に関しては，スリム木カット幅を一般化した木カット幅が定数であっても NP 困難であることを示す． | |||||||||||
| 書誌レコードID | ||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||
| 収録物識別子 | AN1009593X | |||||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2024-AL-199, 号 5, p. 1-7, 発行日 2024-08-29 |
|||||||||||
| ISSN | ||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||
| 収録物識別子 | 2188-8566 | |||||||||||
| Notice | ||||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||||
| 出版者 | ||||||||||||
| 言語 | ja | |||||||||||
| 出版者 | 情報処理学会 | |||||||||||
