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

• Material Type: 博士論文
• Title: 最大クリーク問題の多項式時間的可解性に関する研究
• Author/Editor: 中西, 裕陽; Hiroaki, Nakanishi
• Author Heading: 中西, 裕陽; Hiroaki, Nakanishi
• Publication Date: 2016-12-31
• Publication Date (W3CDTF): 2016-12-31
• Alternative Title: A Study on Polynomial-Time Solvability of the Maximum Clique Problem
• Degree grantor/type: 電気通信大学
• Date Granted: 2016-12-31
• Date Granted (W3CDTF): 2016-12-31
• Dissertation Number: 乙第138号
• Degree Type: 博士（工学）
• Conferring No. (Dissertation): 乙第138号
• Text Language Code: jpn
• Target Audience: 一般
• 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 である連結な誘導部分グラフのうち, 次数最小の節点を除き全く無条件としたもので, 制限条件の大きい緩和である. 以上本論文では, 最大クリーク問題の多項式時間的可解性について, 新しい枠組みを与えた.; 2016
• Persistent ID (NDL): info:ndljp/pid/11008576; https://dl.ndl.go.jp/pid/11008576
• Collection: 障害者向け資料
• Collection (Materials For Handicapped People:1): テキストデータ
• Collection (particular): 国立国会図書館デジタルコレクション > デジタル化資料 > 博士論文; https://dl.ndl.go.jp/collections/A00014
• Acquisition Basis: 博士論文（自動収集）
• Date Accepted (W3CDTF): 2018-01-02T17:18:43+09:00
• Date Created (W3CDTF): 2016-12-19
• Format (IMT): application/pdf
• Access Restrictions: 国立国会図書館内限定公開
• Service for the Digitized Contents Transmission Service: 図書館・個人送信対象外
• Availability of remote photoduplication service: 可
• Periodical Title (URI): http://id.nii.ac.jp/1438/00007916/
• Data Provider (Database): 国立国会図書館 : 国立国会図書館デジタルコレクション; https://dl.ndl.go.jp

Table of Contents

2023-12-07 再収集