- 著者
- 江藤 宏 朝廣 雄一 伊藤 健洋 宮野 英次
- 出版者
- 電気・情報関係学会九州支部連合大会委員会
- 雑誌
- 電気関係学会九州支部連合大会講演論文集
- 巻号頁・発行日
- vol.2013, pp.418, 2013
RIS問題が平面グラフでは近似困難であるが,木幅限定グラフでは線形時間で最適解が求まることを述べる.
1 0 0 0 次数指定した最大正則誘導部分グラフ探索問題(一般)
- 著者
- 朝廣 雄一 伊藤 健洋 江藤 宏 宮野 英次
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. COMP, コンピュテーション
- 巻号頁・発行日
- vol.113, no.198, pp.43-50, 2013-08-27
本稿では,グラフG=(V, E)と指定次数γが与えられたとき,頂点部分集合S によって誘導される部分グラフG[S]が指定した次数rの正則グラフであり,頂点数が最大となるようなSを見つけ出す最適化問題を考える.また,グラフG[S]がr-正則,かつ連結グラフである場合についても考える.両問題は,ある定数rについて,近似することさえNP困難であることが知られている.本稿では,入力を特別なグラフクラスに限定した問題について考える.rをある定数とし,入力グラフを二部グラフまたは平面グラフに限定したとしても,本稿で考える連結性を条件とする正則誘導連結部分グラフ探索問題と必要としない正則誘導部分グラフ探索問題が近似することさえNP困難のままであることを示す.一方,以下のような木構造を持つグラフを入力とした場合には,両問題が簡単になることを示す.まず,木幅限定グラフを入力としたとき,両問題に対する最適解を線形時間で求めるアルゴリズムを示す.ここで,計算時間に隠れている係数は木幅の単一指数である.更に,入力を弦グラフとしたときには,両問題の最適解を多項式時間で求めることができることを示す.
- 著者
- 田村 祐馬 伊藤 健洋 周 暁
- 雑誌
- 研究報告アルゴリズム(AL)
- 巻号頁・発行日
- vol.2014-AL-148, no.3, pp.1-6, 2014-06-06
無向グラフ G のフィードバック点集合 F とは,G から F を取り除くと,残されたグラフが林になるような G の点部分集合のことである.また,F が G の独立点集合をなすとき,F はフィードバック独立点集合という.本稿では,与えられたグラフに対し,点数が最小のフィードバック独立点集合を求める問題について研究する.この問題は,平面的二部グラフに対してさえ NP 困難であることが示せるため,我々はいくつかの特別なグラフクラスに着目する.まず我々は,この問題が木幅制限グラフと弦グラフに対して線形時間で解けることを示す.次に,平面グラフに対しては,解のサイズをパラメータとした FPT アルゴリズムを与える.