最大クリークを抽出する単純で効率的な分枝限定手法
スポンサーリンク
概要
- 論文の詳細を見る
最大クリークを厳密に見つける方法が幾つか研究されてきているが,部分問題に分割を繰り返し探索する時,最終的な分割数すなわち分技数と一つの部分問題にかかる手数を含めた結果が実行時間に結び付く.一般に分枝数を出来るだけ限定することが望ましいが,これにかかる費用が大きすぎるとかえって総実行時間が増大する.本稿では,比較的軽い単純な処理で大きな分枝限定効果を得る手法を提唱し,その実験的評価を行った.
- 一般社団法人情報処理学会の論文
- 1995-03-15
著者
-
富田 悦次
電気通信大学
-
富田 悦次
電気通信大学|中央大学研究開発機構
-
小川 剛
電気通信大学電子情報学科
-
今松 憲一
電気通信大学電気通信学部情報通信工学科
-
木幡 康弘
電気通信大学電気通信学部電子情報学科
-
今松 憲一
電気通信大学電気通信学部情報通信工学科:(現)富士通(株)
-
木幡 康弘
電気通信大学電気通信学部電子情報学科:nttデータ通信株式会社
関連論文
- 最大クリーク問題の多項式時間的可解性の一結果(情報・システム基礎)
- 最大クリーク抽出の単純な最大時間計算量評価と多項式時間的可解性 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 最大クリーク抽出問題の理論計算量評価について : グラフの次数を限定した場合
- 準同型写像によって拡張されたある言語クラスに対する正例からの極限同定
- 実時間空スタック受理式決定性限定ワンカウンタ変換器の多項式時間等価性判定(オートマトン・言語理論)
- 正則言語のある部分クラスに対する正の例からの多項式時間極限同定
- 最大クリーク抽出アルゴリズムの共有メモリ型並列計算機上での並列化
- 極大クリーク全列挙アルゴリズムを用いた企業コミュニティ理解
- 極大クリーク全列挙アルゴリズムを用いた企業コミュニティ理解
- ある種の有限状態変換器に対する多項式時間極限同定