講演抄録/キーワード |
講演名 |
2007-11-22 09:55
クリーク問題と隣接行列に関する一考察 ○小林邦勝(山形大) ISEC2007-99 OIS2007-71 |
抄録 |
(和) |
NP完全問題であるクリーク問題の解法について検討する。クリークとはグラフGの部分グラフの中で次数が最大の完全グラフのことである。kクリーク問題は、グラフGの隣接行列Aの部分行列である、非対角要素がすべて1のk×k行列が存在するか否かを判定する問題と等価である。従って、kクリークが存在するためには、隣接行列において1の数がk-1以上の行ベクトルがk個以上存在することが必要になる。本文では、隣接行列を用いることにより、頂点数がnのグラフGにkクリークが存在するか否かをnの2乗オーダーの計算量で判定するアルゴリズムを提案する。 |
(英) |
We examine a solution of k-clique problem. By using adjacency matrix of graph G, we can decide whether k-clique of graph G is existing or not efficiently. |
キーワード |
(和) |
クリーク問題 / NP完全 / 隣接行列 / NP=P / / / / |
(英) |
clique problem / NP complete / adjacency matrix / NP=P / / / / |
文献情報 |
信学技報, vol. 107, no. 346, ISEC2007-99, pp. 9-13, 2007年11月. |
資料番号 |
ISEC2007-99 |
発行日 |
2007-11-15 (ISEC, OIS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
ISEC2007-99 OIS2007-71 |