最大クリーク問題の多項式時間的可解性の更なる改良結果
スポンサーリンク
概要
- 論文の詳細を見る
NP完全である最大クリーク問題に対して,本稿では,"節点数nの一般グラフにおいて,最大次数ΔがΔ≦2.773dlgn(d≧0:定数)なる条件を満たしているとき,このグラフの最大クリーク問題はO(n^<1+d>)なる多項式時間で可解である."ことを示す.これは,先の発表結果(信学技報,COMP2010-43,pp.29-36)の改良であり,最大次数の上限に関する定数を一層増大させて,この定数2.773を得ている.更に,前発表ではd≧1であった条件をd≧0へと拡張し,dが1よりも小さくて疎なグラフに対しては,時間計算量をO(n^2)よりも小とした.これは,前発表ではグラフを隣接行列で表現することを前提としていたのに対して,本稿では隣接リスト表現を用いることにより実現している.これにより,"最大次数Δが定数である一般グラフにおいて,この最大クリーク問題はO(n)時間で可解である."との結果も得た.
- 2011-04-15
著者
-
中西 裕陽
電気通信大学先進アルゴリズム研究ステーション
-
西野 哲朗
電通大
-
若月 光夫
電気通信大学先進アルゴリズム研究ステーション・電気通信大学情報通信工学科
-
富田 悦次
電気通信大学先進アルゴリズム研究ステーション・中央大学研究開発機構
-
富田 悦次
電気通信大学
-
富田 悦次
Department Of Commucations And Systems Engineering The University Of Electro-communications
-
西野 哲朗
電気通信大学 電気通信学部 情報通信工学科 情報メディア工学講座
-
富田 悦次
電気通信大学|中央大学研究開発機構
-
若月 光夫
電気通信大学大学院情報理工学研究科
-
若月 光夫
電気通信大学先進アルゴリズム研究ステーション・電気通信大学情報理工学研究科
-
若月 光夫
電気通信大学 先進アルゴリズム研究ステーション
-
西野 哲朗
電気通信大学 先進アルゴリズム研究ステーション
-
西野 哲朗
電気通信大学
-
若月 光夫
電気通信大学
-
西野 哲朗
電気通信大学先進アルゴリズム研究ステーション
-
若月 光夫
電気通信大学先進アルゴリズム研究ステーション|電気通信大学大学院情報理工学研究科
関連論文
- 最大クリーク問題の多項式時間的可解性の一結果(情報・システム基礎)
- M.Nakahara and T.Ohmi, QUANTUM COMPUTING;From Linear Algebra to Physical Realizations, CRC Press, USA, 2008, xvi+421p, 24×16cm, $79.95, [大学院向], ISBN978-0-7503-0983-7
- 直方体分割の24次格子グラフ表現とその応用 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 最大クリーク抽出の単純な最大時間計算量評価と多項式時間的可解性 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 第2回UECコンピュータ大貧民大会(UECda-2007)の報告
- インターナルクロックモデルに基づくロボット制御法の実現
- インターナルクロックモデルに基づくロボット制御法の実現(セッション1)
- 小脳顆粒層をモデル化したスパイキングネットワークの研究 : NMDA受容体を介した同期発火状態と時間表現状態の遷移(バイオサイバネティックス,ニューロコンピューティング)
- 小脳顆粒層のスパイキングネットワークモデルにおける状態遷移とタイミングメカニズムに関する研究(機械学習,一般)
- 自由再生実験における記憶の神経回路モデルについて(セッション2)
- 最大クリーク抽出問題の理論計算量評価について : グラフの次数を限定した場合
- 準同型写像によって拡張されたある言語クラスに対する正例からの極限同定
- 実時間空スタック受理式決定性限定ワンカウンタ変換器の多項式時間等価性判定(オートマトン・言語理論)
- E-075 K-means法を用いたジュウシマツの歌の音素分類に関する研究(E分野:自然言語・音声・音楽)
- E-074 可変長Nグラムモデルを用いたジュウシマツの歌構造の解析に関する研究(E分野:自然言語・音声・音楽)
- 最大クリーク問題の多項式時間的可解性の一結果
- UECソフトウェア・リポジトリと実践的ソフトウェア開発教育(知的財産,一般)
- 正則言語のある部分クラスに対する正の例からの多項式時間極限同定
- 量子計算量理論(システムソサイエティ論文賞受賞記念講演)
- NMR量子計算によるNP完全問題と因数分解の解法(量子計算)
- 衝突問題に対する量子アルゴリズムにおけるソーティング方法の選択について(量子計算)
- 最大クリーク問題の多項式時間的可解性の改良結果 (Theoretical foundations of computing)
- コンピュータ大貧民(思考ゲーム)
- 第3回UECコンピュータ大貧民大会(UECda-2008)の報告(大会報告)
- クラスター状態を用いた量子計算への新たなアプローチ
- GPGPUによるGroverのアルゴリズムのシミュレーション
- ノイズ環境化におけるGroverのアルゴリズムのシミュレーション
- 第1回UECコンピュータ大貧民大会(UECda-2006)の実施報告
- 第1回UECコンピュータ大貧民大会(UECda-2O06)の報告
- 量子計算量の下界の評価手法(新世代の計算限界-その解明と打破-招待解説論文)
- 量子計算量理論の最近の展開について(電子デバイス, 一般)
- Bulk量子計算モデル上におけるGroverのアルゴリズムの繰返し回数について
- 物理的実現可能性に優れたNMR量子探索アルゴリズム(計算理論)
- 最大クリーク抽出アルゴリズムの共有メモリ型並列計算機上での並列化
- ある種の有限状態変換器に対する多項式時間極限同定
- 実時間空スタック受理式決定性限定ワンカウンター変換器の多項式時間等価性判定アルゴリズム
- ε-推移を許したある決定性プッシュダウン変換器対の等価性判定(オートマトン・言語理論)
- ε-推移を許したある決定性プッシュダウン変換機器対の等価性判定アルゴリズム(セッション4)
- 小脳スパイキングネットワークモデルにおける条件刺激強度依存性タイミング制御
- 任意形状位置概念をもちいたエージェント行動規則表現
- GPGPUによる Grover のアルゴリズムの大規模シミュレーションについて
- 多人数不完全情報ゲームの簡略化評価値による探索を用いた終盤データベースの構築
- 小脳スパイキングネットワークモデルにおける条件刺激強度依存性タイミング制御
- NMR量子計算機を用いた効率的探索アルゴリズムの設計について
- 衝突問題に対する量子アルゴリズムにおけるソーティング方法の選択について
- NMR量子コンピュータ上における効率的量子探索アルゴリズム
- 正の例から極限同定可能な言語クラスを拡張する統一的アルゴリズム
- 単純でより高速な最大クリーク抽出アルゴリズム
- GPGPUによる Grover のアルゴリズムの大規模シミュレーションについて
- 幼児の言語獲得における「動詞-島」段階のニューロイダルネットによるモデル化(抽出・言語獲得)
- FPGA上に実装した小脳ネットワークモデルにおけるタイミングメカニズムの研究(脳のモデルと生物模倣情報処理1,生物模倣情報処理,機械学習,一般)
- 量子計算と量子アルゴリズム
- 量子計算機による情報処理 (特集:量子効果を用いた通信・処理技術)
- 量子論理回路深さ最小化問題のクリーク問題への還元(クリーク問題と応用)
- グラフ彩色問題における確率アルゴリズムとハイブリッドアルゴリズム
- グラフの近似彩色を行う確率アルゴリズム
- 任意形状位置概念をもちいたエージェント行動規則表現
- 終盤データベースを用いた多人数不完全情報ゲームプレイヤモデル
- RA-001 最大クリーク問題の多項式時間的可解性 : 基本的結果(モデル・アルゴリズム・プログラミング,査読付き論文)
- 最大クリークを抽出するO(2^)-時間の多項式領域アルゴリズム
- 理論評価付き最大クリーク抽出アルゴリズムの実験的評価
- 理論評価付き最大クリーク抽出アルゴリズムの実験的評価
- 最大クリークを抽出するO(2^)-時間の多項式領域アルゴリズム
- 最大クリークを抽出する時間計算量O(2^)の多項式領域アルゴリズム
- 最大クリークを抽出する単純なアルゴリズムの最大次数4のグラフにおける計算量
- 新しい計算パラダイム
- 節点重み最大クリーク抽出アルゴリズムと実験的評価
- 節点重み最大クリーク抽出に基づく量子回路の深さ最小化 (計算機科学基礎理論の新展開)
- 節点重み最大クリーク抽出アルゴリズム (計算機科学基礎理論の新展開)
- 量子情報科学の未来--情報セキュリティの観点から (特集 量子情報科学の新時代--量子へと向かう情報とは何か?)
- 量子ゲーム理論 (特集 量子情報科学の新時代--量子へと向かう情報とは何か?)
- 最大クリーク問題の多項式時間的可解性の更なる改良結果 (コンピュテーション)
- 最大クリーク問題の多項式時間的可解性の新たな結果
- 最大クリーク問題の多項式時間的可解性の改良結果
- 量子セルオートマトンに基づく画像圧縮のための画像変換アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)
- 実時間最終状態受理式決定性限定1カウンタ変換器の多項式時間等価性判定アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)
- 最大クリーク問題の多項式時間的可解性について (計算機科学とアルゴリズムの数理的基礎とその応用)
- UMLパッケージ図に対するグラフ文法とその応用
- コンピュータ大貧民に対するモンテカルロ法の適用
- 大貧民における相手手札推定
- Liquid state machineを用いたタイミング制御システムの研究
- 最大クリーク問題の多項式時間的可解性の改良結果(情報・システム基礎)
- 多人数不完全情報ゲームのモンテカルロ木探索における推定の効果
- 多人数不完全情報ゲームのモンテカルロ木探索における推定の効果
- B Methodにおける高信頼ソフトウェア部品自動生成
- 最大クリーク問題の多項式時間的可解性の更なる改良結果
- 最大クリーク問題の多項式時間的可解性の改良結果
- 最大クリーク問題の多項式時間的可解性の更なる改良結果(情報・システム基礎)
- 最大クリーク問題の多項式時間的可解性の拡張
- 最大クリーク問題の多項式時間的可解性の更なる改良結果
- 8次格子モデルによる表の行/列操作 (アルゴリズムと計算理論の新展開)
- 最大クリーク問題の多項式時間的可解性の拡張の改良 (Theoretical Foundations of Computing)
- 最大クリーク問題の多項式時間的可解性の拡張(情報・システム基礎)
- 量子計算量の理論 (特集 量子情報技術--最前線からの展望)
- 量子コンピュータ (特集 コミュニケーションの現在・2003) -- (コンピュータ科学の現在)
- コンピュータ大貧民(娯楽のOR)
- 格助詞によるクラスタリングを用いた分布類似度計算の高速化
- ソースコードモジュール重要度算出法の提案 (理論計算機科学の新展開)
- 最大クリーク問題の多項式時間的可解性の拡張の改良
- 最大クリーク問題の多項式時間的可解性の拡張の更なる改良