講演抄録/キーワード |
講演名 |
2012-09-03 10:50
最大クリーク問題の多項式時間的可解性の拡張の改良 ○中西裕陽・富田悦次・若月光夫・西野哲朗(電通大) COMP2012-28 |
抄録 |
(和) |
典型的なNP完全問題である最大クリーク問題に対し,本稿では,次の結果を示す:
``任意の隣接2節点p,qに対して min(deg(p), deg(q))≦3.177dlgn (d≧0: 定数)なる条件が満たされているとき,このグラフの最大クリーク問題は
O(n^(2+max(d, 1))$なる多項式時間で可解である.
ただし,deg(r)は節点rの次数."
ここで,隣接2節点p,qに対する条件において,max(deg(p), deg(q))=deg(q)
であり,節点qがdeg(q)よりも次数の大きい節点に隣接していないならば,節点
qに対する次数の条件は何ら課さない.
筆者らはこれに先立ち, 同様の定義でmin(deg(p), deg(q))≦2.994dlgn
(d≧0:定数)である場合に同様の結果を得ているが, 本稿では, 前結果における
状況をより詳細に解析した上で, 最大時間計算量が大きくなる場合に対して,
更に詳細な場合分けを伴ったアルゴリズムと時間計算量解析を導入することにより, 本結果を得ている. |
(英) |
This paper presents an improved extended result for polynomial-time solvability of the maximum clique problem, that is:
for any adjacent pair of vertices p and q where the degree of p is
less than or equal to that of q in a graph with n vertices,
if the degree of p is less than or equal to 3.177dlgn
(d≧0: a constant),
then the maximum clique problem is solvable in the polynomial time of O(n^(1+d)).
This result is obtained by detailed case analysis and the corresponding detailed algorithm. |
キーワード |
(和) |
NP完全 / 最大クリーク / 深さ優先探索 / 時間計算量 / 節点次数 / / / |
(英) |
NP-Complete / Maximum Clique / Depth-First Search / Time-Complexity / Degree of a vertex / / / |
文献情報 |
信学技報, vol. 112, no. 199, COMP2012-28, pp. 17-24, 2012年9月. |
資料番号 |
COMP2012-28 |
発行日 |
2012-08-27 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2012-28 |