動的計画法を用いた上界計算法による最大重みクリーク抽出アルゴリスムの提案(一般)
スポンサーリンク
概要
- 論文の詳細を見る
頂点に重みが付与された無向グラフが与えられたとき,重みが最大となるクリークを求める問題を最大重みクリーク問題という.本稿では最大重みクリーク問題に対して,分枝限定法に基づく厳密解法を提案する.分枝限定法では,探索の際に現れる部分問題に対し,解の上限を計算する.提案手法では探索を開始する前に小さな部分問題をいくつか作成し,それらの厳密解を動的計画法で計算し記録しておく.分枝限定法において現れる各部分問題の解の上限について,記録しておいた値を用いて手間をかけず高速に計算する.Cliquerなどいくつかの従来手法との比較実験を行い,提案手法の有効性を確認した.
- 2013-03-11
著者
関連論文
- 空間に埋め込まれた木の距離とその計算法
- 類似データ検索のためのファイル構成法
- グラフ描画の直交格子への埋込アルゴリズムとデフォルメ路線図作成への応用(グラフとネットワーク)
- ラベル配置可能領域とルール処理を用いたラベル配置アルゴリズム(研究速報)
- 有向グラフ描画アルゴリズムにおける閉路削除法の改良
- 5M-8 点パターン検索のためのアルゴリズムの提案(アルゴリズム,学生セッション,ソフトウェア科学・工学)
- 局所探索法による階層的描画の辺交差削減(研究速報)
- 一般化したラベルサイズ最大化問題に対するアルゴリズム(研究速報)
- 力指向グラフ描画アルゴリズムにおける頂点移動方法の改良(研究速報)
- D-1-5 有向グラフ描画アルゴリズムにおける閉路削除法の改良(D-1. コンピュテーション,一般セッション)
- 地理データに対する領域隣接グラフを利用した領域管理手法(研究速報)
- 階層グラフ描画におけるダミー頂点の共有(アルゴリズムとデータ構造・計算複雑度)
- 階層グラフ描画における頂点座標決定アルゴリズム(グラフとネットワーク)
- 5.ZDDを用いた新たな列挙手法(広がる列挙の技術-列挙による問題解決アプローチ-)
- 全頂点のラベルを配置したグラフ描画を求めるアルゴリズム(グラフとネットワーク)
- 文字列の縦書きと折返しを許したラベル配置アルゴリズム(研究速報)
- 動的計画法を用いた有向二値完全系統樹の効率のよい列挙
- 不完全データと矛盾しない有向二値完全系統樹を列挙する効率的手法
- 動的計画法を用いた上界計算法による最大重みクリーク抽出アルゴリスムの提案(一般)
- 動的計画法を用いた有向二値完全系統樹の効率のよい列挙(一般)
- 階層グラフの直交描画アルゴリズム
- 階層グラフの直交描画アルゴリズム(グラフとネットワーク)