最大クリーク問題の多項式時間的可解性の拡張の更なる改良

• Item type: SIG Technical Reports(1)
• 公開日: 2014-06-06
• タイトル: 最大クリーク問題の多項式時間的可解性の拡張の更なる改良
• タイトル / 言語: en
• タイトル: A Further Improved Extended Result on Polynomial-Time Solvability of the Maximum Clique Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 電気通信大学先進アルゴリズム研究ステーション／早稲田大学教育学部数学科
• 著者所属: 電気通信大学先進アルゴリズム研究ステーション／科学技術振興機構 ERATO 湊離散構造処理系プロジェクト／東京工業大学大学院情報理工学研究科
• 著者所属: 電気通信大学先進アルゴリズム研究ステーション／電気通信大学大学院情報理工学研究科
• 著者所属: 電気通信大学先進アルゴリズム研究ステーション／電気通信大学大学院情報理工学研究科
• 著者所属(英): en
• 著者所属(英): The Advanced Algorithms Research Laboratory, The University of Electro-Communications / Department of Mathematics, School of Education, Waseda University
• 著者所属(英): en
• 著者所属(英): The Advanced Algorithms Research Laboratory, The University of Electro-Communications / JST ERATO Minato Discrete Structure Manipulation System Project / Graduate School of Information Science and Engineering, Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): The Advanced Algorithms Research Laboratory, The University of Electro-Communications / Graduate School of Informatics and Engineering, The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): The Advanced Algorithms Research Laboratory, The University of Electro-Communications / Graduate School of Informatics and Engineering, The University of Electro-Communications
• 著者名: 中西, 裕陽; 富田, 悦次; 若月, 光夫; 西野, 哲朗
• 著者名(英): Hiroaki, Nakanishi; Etsuji, Tomita; Mitsuo, Wakatsuki; Tetsuro, Nishino
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: NP 完全である最大クリーク問題に対し，“節点数 n≧１ のグラフにおいて，グラフ中の任意の隣接 2 節点 vi,vj∈V, (vi,vj)∈E が min{deg(vi), deg(vj)}≦3.486d lg n (d ≧0: 定数) を満たすならば，最大クリーク問題は O(n2+max{d,1}) 時間で解決可能である．” ことを示す．これは，先に発表した結果 (信学論 (D)，vol.J97-D，no.6，June 2014) の定量的改良である．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper presents a further 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.486d lg n (d≧0: a constant), then the maximum clique problem is solvable in the polynomial time of O(n2+max{d,1}). This result is obtained by more detailed analysis and the corresponding detailed algorithm.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2014-AL-148, 号 14, p. 1-8, 発行日 2014-06-06
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会