| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2007-06-29 09:00 最大クリークを抽出する単純なアルゴリズムの最大次数4のグラフにおける計算量 ○中西裕陽・富田悦次（電通大）  COMP2007-18 |
|
| 抄録 | （和） | 無向グラフ中の最大クリークを抽出する問題はNP困難であり, 自明な計算量が O(P(n)2^n)(P(n)は節点数nの多項式)という困難な問題であって, その計算量を改善する多くの試みがなされている. ここでは極大クリーク全列挙アルゴリズムCLIQUESを基にして, これに分枝限定処理を導入した単純な最大クリーク抽出アルゴリズムを提示する. 最終的な目的はこのアルゴリズムを用いて一般グラフに対する最大クリーク抽出 の計算量上界を改善することであるが, 本稿ではその基礎的な段階として, 最大次数4以下という非常に単純なグラフを扱い, これらにおいては上界が O(n^3)となることを示す. |
| （英） | The maximum clique problem is an NP-hard problem, and is difficult to solve efficiently. The trivial upper bound of its time complexity is O(P(n)2^n), where P(n) is a polynomial of n, the number of vertices. Several improvements have been done for this upper bound. In this note, we present a simple branch-and-bound algorithm for the maximum clique problem. It is based on our preceeding algorithm CLIQUES, which is designed for generating all maximal cliques. We aim to prove that our algorithm improves the upper bound for finding a maximum clique in a general graph, and we show here that it has O(n^3) upper bound in a graph with maximum degree 4, as a basis of the analysis for a general case. |
|
| キーワード | （和） | NP困難 / 最大クリーク / 最大独立節点集合 / 時間計算量 / / / / |
| （英） | NP-hard / Maximum clique / Maiximum independent set / Time complexity / / / / | |
| 文献情報 | 信学技報, vol. 107, no. 127, COMP2007-18, pp. 1-7, 2007年6月. | |
| 資料番号 | COMP2007-18 | |
| 発行日 | 2007-06-22 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2007-18 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2007-06-29 - 2007-06-29 |
| 開催地（和） | 北海道大学 |
| 開催地（英） | Hokkaido University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2007-06-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | 最大クリークを抽出する単純なアルゴリズムの最大次数4のグラフにおける計算量 |
| サブタイトル（和） | |
| タイトル（英） | A Computaional Complexity for finding a Maximum Clique in a Graph with Maximum Degree 4 |
| サブタイトル（英） | |
| キーワード(1)（和/英） | NP困難 / NP-hard |
| キーワード(2)（和/英） | 最大クリーク / Maximum clique |
| キーワード(3)（和/英） | 最大独立節点集合 / Maiximum independent set |
| キーワード(4)（和/英） | 時間計算量 / Time complexity |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 中西 裕陽 / Hiroaki Nakanishi / ナカニシ ヒロアキ |
| 第1著者 所属（和/英） | 電気通信大学 (略称： 電通大) The University of Electro-Communications (略称： UEC) |
| 第2著者 氏名（和/英/ヨミ） | 富田 悦次 / Etsuji Tomita / トミタ エツジ |
| 第2著者 所属（和/英） | 電気通信大学 (略称： 電通大) The University of Electro-Communications (略称： UEC) |
| 講演者 | 第1著者 |
| 発表日時 | 2007-06-29 09:00:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2007-18 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | no.127 |
| ページ範囲 | pp.1-7 |
| ページ数 | 7 |
| 発行日 | 2007-06-22 (COMP) |
[研究会発表申込システムのトップページに戻る]