最大クリーク問題の多項式時間的可解性に関する研究

Persistent ID (NDL): info:ndljp/pid/10233497

Material type: 博士論文

Author: 中西, 裕陽ほか

Publisher: The University of Electro-Communications

Publication date: 2016-12-31

Material Format: Digital

Capacity, size, etc.: -

Name of awarding university/degree: 電気通信大学,博士（工学）

View All

Notes on use at the National Diet Library

本資料は、掲載誌(URI)等のリンク先にある学位授与機関のWebサイトやCiNii Dissertationsから、本文を自由に閲覧できる場合があります。

Notes on use

Note (General)：: いわゆる“最大クリーク問題”は典型的なNP 完全問題であり, 多項式時間的に本問題を解くことはほぼ不可能であると強く予測されている．従って, 少なくともどのような条件下ならばこのNP 完全問題を多項式時間的に解くことが出来るかを明らかにすることは重要な課題である．これに対し, 平面グラフ, コーダル...

Search by Bookstore

Read this material in an accessible format.

View materials in accessible formats for people with print disabilities (1Type)

Search by Bookstore

Read in Disability Resources

Other Services
- テキストデータ check it on 国立国会図書館デジタルコレクション

Bibliographic Record

You can check the details of this material, its authority (keywords that refer to materials on the same subject, author's name, etc.), etc.

Digital

Material Type: 博士論文
Title: 最大クリーク問題の多項式時間的可解性に関する研究
Author/Editor: 中西, 裕陽
ナカニシ, ヒロアキ
Nakanishi, Hiroaki
Publication, Distribution, etc.: The University of Electro-Communications
Publication Date: 2016-12-31
Publication Date (W3CDTF): 2016-12-31
Alternative Title: サイダイクリークモンダイノタコウシキジカンテキカカイセイニカンスルケンキュウ
A Study on Polynomial-Time Solvability of the Maximum Clique Problem
Periodical title: 学位論文
Degree grantor/type: 電気通信大学
Date Granted: 2016-12-31
Date Granted (W3CDTF): 2016-12-31
Dissertation Number: 乙第138号
Degree Type: 博士（工学）
Conferring No. (Dissertation): 12612乙第138号
Text Language Code: jpn
Note (General): いわゆる“最大クリーク問題”は典型的なNP 完全問題であり, 多項式時間的に本問題を解くことはほぼ不可能であると強く予測されている．従って, 少なくともどのような条件下ならばこのNP 完全問題を多項式時間的に解くことが出来るかを明らかにすることは重要な課題である．これに対し, 平面グラフ, コーダルグラフ等いくつかの特殊グラフに対しては多項式時間的可解性が成立することが示されている. しかし一般グラフにおいては, 最大クリーク問題が多項式時間的可解となる条件について, これまでにおいて有意義な定量的結果は発表されていなかった. そこで本研究では, 先ず極大クリーク全列挙アルゴリズムCLIQUES (E. Tomita, A. Tanaka, H. Takahashi: Theoretical Computer Science, 2006) を基にして, 基本的な最大クリーク抽出の深さ優先探索アルゴリズムを確立した. この基本的アルゴリズムに対して探索領域限定操作をより強力化し, 対応したより詳細な場合分けを伴った解析を行うことにより, アルゴリズムが多項式時間的に終端する条件を逐次緩和し, 次の定量的な多項式時間的可解性条件を与えた．即ち, 先ず一般グラフにおいてグラフの最大次数Δ のみを条件とした, 最大クリーク問題に対する以下の多項式時間的可解性の成立を示した. 「節点数n のグラフG = (V,E) の最大次数Δ が,Δ<_3:177d lgn (d>_0:定数) なる条件を満たすとき, 最大クリーク問題はO(n1+d) なる多項式時間で可解である. 」さらに本研究においては, 全節点に対する前記条件をより緩和した, 次の拡張結果も与えた. 「サイズn0>_2 なる任意の連結な誘導部分グラフG(C)( C⊆V ) に対して, C 中の最小次数節点v が, deg(v)<_3.177d lgn (d>_0:定数) を満たすとき, 最大クリーク問題はO(nmax(2,1+d)) の多項式時間で可解である. 」これは, サイズn0 である連結な誘導部分グラフのうち, 次数最小の節点を除き全く無条件としたもので, 制限条件の大きい緩和である. 以上本論文では, 最大クリーク問題の多項式時間的可解性について, 新しい枠組みを与えた.
開始ページ : 1
終了ページ : 170
Persistent ID (NDL): info:ndljp/pid/10233497
https://dl.ndl.go.jp/pid/10233497
Collection: 障害者向け資料
Collection (Materials For Handicapped People:1): テキストデータ
Collection (particular): 国立国会図書館デジタルコレクション > デジタル化資料 > 博士論文
https://dl.ndl.go.jp/collections/A00014
Acquisition Basis: 博士論文（自動収集）
Date Accepted (W3CDTF): 2017-01-01T19:17:28+09:00
Format (IMT): application/pdf
Access Restrictions: 国立国会図書館内限定公開
Service for the Digitized Contents Transmission Service: 図書館・個人送信対象外
Availability of remote photoduplication service: 可
Periodical Title (URI): http://hdl.handle.net/10480/9000000875
Data Provider (Database): 国立国会図書館 : 国立国会図書館デジタルコレクション
https://dl.ndl.go.jp