WEKO3
アイテム
フィードバック独立点集合問題
https://ipsj.ixsq.nii.ac.jp/records/101690
https://ipsj.ixsq.nii.ac.jp/records/1016908fff03ba-9137-47ed-9d9b-d89d26cb666d
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL14148003.pdf (345.3 kB)
2100年1月1日からダウンロード可能です。
|
Copyright (c) 2014 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG.
|
|
| AL:会員：¥0, DLIB:会員：¥0 | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2014-06-06 | |||||||
| タイトル | ||||||||
| タイトル | フィードバック独立点集合問題 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | The Independent Feedback Vertex Set Problem | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 東北大学大学院情報科学研究科／国立情報学研究所ビッグデータ数理国際研究センターJSTERATO河原林巨大グラフプロジェクト | ||||||||
| 著者所属 | ||||||||
| 東北大学大学院情報科学研究科 | ||||||||
| 著者所属 | ||||||||
| 東北大学大学院情報科学研究科 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Information Sciences, Tohoku University / JST, ERATO, Kawarabayashi Large Graph Project, c/o Global Research Center for Big Data Mathematics, NII | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Information Sciences, Tohoku University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Information Sciences, Tohoku University | ||||||||
| 著者名 |
田村, 祐馬
× 田村, 祐馬
|
|||||||
| 著者名(英) |
Yuma, Tamura
× Yuma, Tamura
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 無向グラフ G のフィードバック点集合 Ｆ とは，G から F を取り除くと，残されたグラフが林になるような G の点部分集合のことである．また，Ｆ が G の独立点集合をなすとき，Ｆ はフィードバック独立点集合という．本稿では，与えられたグラフに対し，点数が最小のフィードバック独立点集合を求める問題について研究する．この問題は，平面的二部グラフに対してさえ NP 困難であることが示せるため，我々はいくつかの特別なグラフクラスに着目する．まず我々は，この問題が木幅制限グラフと弦グラフに対して線形時間で解けることを示す．次に，平面グラフに対しては，解のサイズをパラメータとした FPT アルゴリズムを与える． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | A feedback vertex set F of an undirected graph G is a vertex subset of G whose removal results in a forest. Such a set F is said to be independent if F forms an independent set of G. In this paper, we study the problem of finding an independent feedback vertex set of a given graph with the minimum number of vertices. This problem is NP-hard even for planar bipartite graphs, and hence we focus on some special classes of graphs. We first show that the problem is solvable in linear time for bounded treewidth graphs and chordal graphs. Then, we give an FPT algorithm for planar graphs when parameterized by the solution size. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2014-AL-148, 号 3, p. 1-6, 発行日 2014-06-06 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
