お知らせ 研究会の開催と会場に参加される皆様へのお願い(2020年7月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2011-04-22 13:55
最大クリーク問題の多項式時間的可解性の更なる改良結果
中西裕陽電通大)・富田悦次電通大/中大)・若月光夫西野哲朗電通大COMP2011-6
抄録 (和) NP完全である最大クリーク問題に対して,本稿では,``節点数nの一般グラフにおいて,最大次数ΔがΔ ≦ 2.773dlg n (d ≧ 0: 定数)なる条件を満たしているとき,このグラフの最大クリーク問題はO(n^{1+d})なる多項式時間で可解である." ことを示す.これは,先の発表結果(信学技報, COMP2010-43, pp.29--36)の改良であり,最大次数の上限に関する定数を一層増大させて,この定数2.773を得ている. 更に,前発表ではd ≧ 1であった条件をd ≧ 0へと拡張し,dが1よりも小さくて疎なグラフに対しては,時間計算量をO(n^2)よりも小とした.これは,前発表ではグラフを隣接行列で表現することを前提としていたのに対して,本稿では隣接リスト表現を用いることにより実現している.これにより,``最大次数Δが定数である一般グラフにおいて,この最大クリーク問題はO(n)時間で可解である." との結果も得た. 
(英) This report presents a further improved result for polynomial-time solvability of the maximum clique problem, that is: for a graph with n vertices, if the maximum degree Δ is less than or equal to 2.773dlg n (d ≧ 0: a constant), then the maximum clique problem is solvable in the polynomial time of O(n^{1+d}). This is an improvement of our preceding result in Tech. Rep. IEICE, COMP2010-43, pp.29--36. The present result is established for a graph represented by an adjacency list. As a result, we show that the maximum clique problem is solvable in O(n)-time if the maximum degree of a graph is a constant.
キーワード (和) NP完全 / 最大クリーク / 深さ優先探索 / 時間計算量 / 最大次数 / / /  
(英) NP-Complete / Maximum Clique / Depth-First Search / Time-Complexity / Maximum Degree / / /  
文献情報 信学技報, vol. 111, no. 20, COMP2011-6, pp. 41-48, 2011年4月.
資料番号 COMP2011-6 
発行日 2011-04-15 (COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード COMP2011-6

研究会情報
研究会 COMP  
開催期間 2011-04-22 - 2011-04-22 
開催地(和) 京都大学 
開催地(英) Kyoto University 
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2011-04-COMP 
本文の言語 日本語 
タイトル(和) 最大クリーク問題の多項式時間的可解性の更なる改良結果 
サブタイトル(和)  
タイトル(英) A further improved result on polynomial-time solvability of the maximum clique problem 
サブタイトル(英)  
キーワード(1)(和/英) NP完全 / NP-Complete  
キーワード(2)(和/英) 最大クリーク / Maximum Clique  
キーワード(3)(和/英) 深さ優先探索 / Depth-First Search  
キーワード(4)(和/英) 時間計算量 / Time-Complexity  
キーワード(5)(和/英) 最大次数 / Maximum Degree  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 中西 裕陽 / Hiroaki Nakanishi / ナカニシ ヒロアキ
第1著者 所属(和/英) 電気通信大学 (略称: 電通大)
University of Electro-Communications (略称: UEC)
第2著者 氏名(和/英/ヨミ) 富田 悦次 / Etsuji Tomita / トミタ エツジ
第2著者 所属(和/英) 電気通信大学/中央大学 (略称: 電通大/中大)
University of Electro-Communications/Chuo University (略称: UEC/Chuo Univ.)
第3著者 氏名(和/英/ヨミ) 若月 光夫 / Mitsuo Wakatsuki / ワカツキ ミツオ
第3著者 所属(和/英) 電気通信大学 (略称: 電通大)
University of Electro-Communications (略称: UEC)
第4著者 氏名(和/英/ヨミ) 西野 哲朗 / Tetsuro Nishino / ニシノ テツロウ
第4著者 所属(和/英) 電気通信大学 (略称: 電通大)
University of Electro-Communications (略称: UEC)
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2011-04-22 13:55:00 
発表時間 35 
申込先研究会 COMP 
資料番号 IEICE-COMP2011-6 
巻番号(vol) IEICE-111 
号番号(no) no.20 
ページ範囲 pp.41-48 
ページ数 IEICE-8 
発行日 IEICE-COMP-2011-04-15 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会