著者

佐久間 俊慎 小野 廣隆 山下 雅史 朝廣 雄一 牧野 和久 堀山 貴史

出版者

京都大学数理解析研究所

雑誌

数理解析研究所講究録 (ISSN:18802818)

巻号頁・発行日

vol.1325, pp.8-14, 2003-05

著者

江藤 宏 朝廣 雄一 伊藤 健洋 宮野 英次

出版者

電気・情報関係学会九州支部連合大会委員会

雑誌

電気関係学会九州支部連合大会講演論文集

巻号頁・発行日

vol.2013, pp.418, 2013

---

RIS問題が平面グラフでは近似困難であるが,木幅限定グラフでは線形時間で最適解が求まることを述べる.

著者

三溝 和明 朝廣 雄一 宮野 英次

出版者

情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2010, no.4, pp.1-8, 2010-02-26

参考文献数

15

---

本稿では直径 d 部分グラフ最大化問題 (MaxDBS 問題) について考察する.MaxDBS 問題の目的は,入力グラフ G と整数 d≥1 に対して,直径 d である最大部分グラフを G 中から見つけることである.MaxDBS 問題は,d=1 の場合,よく知られた最大クリーク問題と同一であるので,P≠NP の仮定の下で,任意のε>0 に対して n1-ε よりも良い近似度の近似アルゴリズムは存在しない.また d≥2 に対しては,任意の ε>0 に対して n1/3-ε よりも良い近似度の近似アルゴリズムは存在しないことが知られていた.まず本稿では,この結果を改善し,任意の ε>0 に対して n1/2-ε よりも良い近似度の近似アルゴリズムは存在しないことを示す.また,d が偶数の場合には n1/2 -近似アルゴリズム,d が 3 以上の奇数の場合には n2/3 -近似アルゴリズムが存在することを示す.さらに,弦グラフ,スプリットグラフ,区間グラフ,k 部グラフといった制限された入力に対する近似可能性と近似困難性について考察する.The maximum diameter-bounded subgraph problem (MaxDBS for short) is defined as follows: Given an n-vertex graph G and a fixed integer d ? 1, we are asked to find the largest subgraph of the diameter d in G. If d = 1, the problem is identical to the well known maximum clique problem and thus it is NP-hard to approximate MaxDBS to within a factor of n1-ε for any ε > 0. Also, it is known to be NP-hard to approximate MaxDBS to within a factor of n1/3-ε for any ε > 0 and a fixed d ? 2. In this paper, we first strengthen this hardness result; we prove that, for any ε > 0 and a fixed d ? 2, it is NP-hard to approximate MaxDBS to within a factor of n1/2-ε. Then, we show that a simple polynomial-time algorithm achieves an approximation ratio of n1/2 for any even d ? 2, and an approximation ratio of n2/3 for any odd d ? 3. Furthermore, the (in)tractability and the (in)approximability of MaxDBS on subclasses of graphs are discussed for chordal graphs, split graphs, interval graphs, and k-partite graphs.

著者

朝廣 雄一 伊藤 健洋 江藤 宏 宮野 英次

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. 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困難のままであることを示す.一方,以下のような木構造を持つグラフを入力とした場合には,両問題が簡単になることを示す.まず,木幅限定グラフを入力としたとき,両問題に対する最適解を線形時間で求めるアルゴリズムを示す.ここで,計算時間に隠れている係数は木幅の単一指数である.更に,入力を弦グラフとしたときには,両問題の最適解を多項式時間で求めることができることを示す.

著者

朝廣 雄一 宮野 英次 宮崎 修一 吉牟田 拓朗

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.106, no.405, pp.15-22, 2006-11-27

---

グラフ上での地図作成問題とは,探索者が未知のグラフの全ての頂点を訪問することによりグラフ構造を調査する問題である.探索者は辺の存在とその長さをその端点を訪れるまで判らないとする.探索者は,できるだけ短い経路を通ることにより全ての頂点と辺を調査して,出発点まで戻って来なければならない.本問題に対する最も単純な方法の一つは,最近傍アルゴリズム(NN)であり,まだ訪れていない頂点の中で探索者の現在の場所から最も近い場所に移動する戦略である.重み付き最近傍アルゴリズム(WNN)は,NNの拡張であり,ある重み付きの距離により次の移動場所を決める.平面グラフにおいては,重み3であるWNNが16競合であることが知られている.本稿ではサイクルグラフについては,NNの競合比が1.5となること,その解析が厳密であることを示す.また,サイクルグラフに対してはWNNの中でNNが最適であることを示す.さらに,本問題に対しては,1.25競合よりも良いアルゴリズムが存在しないことを示す.