グラフの最大誘導木を抽出する精度の高い発見的解法(一般)
スポンサーリンク
概要
- 論文の詳細を見る
グラフの最大誘導木抽出問題(以下,MAXIT)とは、「与えられたグラフにおける誘導部分グラフが木となる頂点集合のうちで,点数最大なものを求めよ.」と定義される.この問題はNP困難であることが知られており,発見的解法が既にいくつか提案されている.本稿では,その中で比較的高速な隣接点付加に基づく解法に着目する.隣接点の選択ルールを種々改善することによって解の高精度化を図り,計算機実験によってそれらの効果を検証する.
- 2010-07-26
著者
-
渡邉 敏正
広島大学大学院工学研究科
-
吉田 浩之
広島大学大学院工学研究科
-
高藤 大介
広島大学大学院工学研究科
-
度邉 敏正
広島大学 大学院 工学研究科
-
吉田 浩之
広島大学大学院 工学研究科
-
渡邉 敏正
広島大学大学院 工学研究科
-
高藤 大介
広島大学大学院 工学研究科
関連論文
- 点次数の増加上限制約を持つ2点連結グラフに対する線形時間3点連結化アルゴリズム
- カンファレンスに対するセッションスケジューリングシステムの開発(ライフログ活用技術,オフィス情報システム,マルチメディアシステム,マルチメディア通信,IP放送/映像伝送,一般)
- カンファレンスに対するセッションスケジューリングシステムの開発(オフィス情報システム,ライフログ活用技術,オフィス情報システム,マルチメディアシステム,マルチメディア通信,IP放送/映像伝送,一般)
- 組合せ最適化問題の計算複雑度解析とアルゴリズム設計
- Web-GISに基づく不動産ナビゲーションシステム"賀茂ナビ" : 情報管理機能とインターフェースの改良(オフィスインフォメーションシステム,ディジタルドキュメント、一般)
- メタWebシステム"GECOD'の開発に関する報告 : 生成されるWebシステムの認証機能・権限付与と基礎的機能について(システム構築,ライフログ活用技術,オフィス情報システム,ライフインテリジェンス)
- 端子頂点グラフの全域平面部分グラフ抽出法に対する切断対とネット描画変更に基づく高精度化
- グラフの最大誘導木を抽出する発見的解法の点除去に基づく性能強化
- グラフの最大誘導木抽出法の計算機実験による性能評価(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 辺重み付きカクタスにおけるネット分割に基づく発火系列探索(コンカレント工学及びハイブリッドダイナミカルシステムの理論と応用,一般)
- 各トランジションの発火が2回以下である辺重み付きカクタスにおける発火系列探索
- 障害物を持つ格子スタイナー木問題に対する高速・高精度近似解法(ネットワークプロセッサ, 通信のための信号処理, 符号理論, 一般)
- 障害物を持つ格子スタイナー木問題に対する高速・高精度近似解法(ネットワークプロセッサ, 通信のための信号処理, 符号理論, 一般)
- 障害物を持つ格子スタイナー木問題に対する高速・高精度近似解法(ネットワークプロセッサ, 通信のための信号処理, 符号理論, 一般)
- 障害物を持つ格子スタイナー木問題に対する高速・高精度近似解法
- 障害物を持つ格子スタイナー木問題に対する高速・高精度近似解法
- 障害物を持つ格子スタイナー木問題に対する高速・高精度近似解法
- 障害物を有する格子スタイナー木問題に対する発見的アルゴリズムAGRF
- CGIに基づくデータ送受信・編集・表示のためのメタシステムGECOD(Webサービスベースのオフィスアプリケーション・ネットワーキング・マネジメント及び一般)
- CGIに基づくデータ送受信・編集・表示のためのメタシステムGECOD(Webサービスベースのオフィスアプリケーション・ネットワーキング・マネジメント及び一般)
- CGIに基づくデータ送受信・編集・表示のためのメタシステムGECOD(Webサービスベースのオフィスアプリケーション・ネットワーキング・マネジメント及び一般)
- グラフの最大誘導木を抽出する精度の高い発見的解法(一般)
- グラフの最大誘導木を抽出する精度の高い発見的解法(一般)
- Web-GISに基づく不動産ナビゲーションシステム"賀茂ナビ" : 情報管理機能とインターフェースの改良(オフィスインフォメーションシステム,ディジタルドキュメント、一般)
- k辺連結2部グラフの(k + 1) 辺連結化のための高速アルゴリズム
- Webシステム生成のための仕様整合化機能を有するメタシステム(オフィスインフォメーションシステム及び一般)
- 抑止辺を持つペトリネットにおける発火系列問題解法の実験的評価(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- 抑止辺を持つペトリネットにおける発火系列問題について(コンカレント工学及びハイブリッドダイナミカルシステムの理論と応用,一般)
- ステートマシン構造を持つ抑止ペトリネットの発火系列問題(コンカレント工学一般)
- 広島大学生物圏科学研究科における教育記録システムの開発(マルチメディア通信,マルチメディアシステム,ライフログ活用技術、IP放送/映像伝送,一般)
- 広島大学生物圏科学研究科における教育記録システムの開発(マルチメディア通信,マルチメディアシステム,ライフログ活用技術、IP放送/映像伝送,一般)
- 組合せ最適化問題の計算複雑度解析とアルゴリズム設計
- 抑止辺を持つペトリネットの発火系列問題の解法について(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 抑止辺を持つペトリネットの発火系列問題の解法について(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 抑止辺を持つペトリネットの発火系列問題の解法について(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- トークン供給フロー制御と競合トランジションに基づく後退操作によるペトリネット発火系列探索法の性能強化
- MAX-LFS解法と後処理の改良により性能強化されたペトリネットのマーキング構成問題解法
- グラフの最大誘導木の発見的抽出法(グラフ,ペトリネット,ニューラルネット,及び一般)
- グラフの最大誘導木の発見的抽出法(グラフ,ペトリネット,ニューラルネット,及び一般)
- A-12-1 D-サイフォン縮小に基づくペトリネットの最小初期マーキング問題解法AMDLO(A-12.コンカレント工学,一般セッション)
- トランジションの超過発火を許したペトリネットの発火系列探索法(コンカレント工学一般、及び、CSTソリューションコンペティション2007発表会)
- ペトリネットの初期マーキング最少化のための発見的アルゴリズムAADO(グラフ,ペトリネット,ニューラルネット及び一般)
- ペトリネットの初期マーキング最少化のための発見的アルゴリズムAADO(グラフ,ペトリネット,ニューラルネット及び一般)
- ペトリネットのサイフォン・トラップ抽出に基づくFourier-Motzkin法の安定性向上(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- ペトリネットマーキング構成問題に対する発火系列探索法の改良(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- 指定プレースをサポートに含む極小サポートインバリアントのサイフォン・トラップに基づく算出法(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- ペトリネットの最小初期マーキング探索におけるトランジションの効果的選択法(コンカレントシステム, 一般)
- ペトリネットの最小初期マーキングのための動作的デッドロック回避に基づく高速な発見的解法(コンカレントシステム, 離散事象システム, ハイブリッドシステム, 及び一般)
- ペトリネットの発火系列探索におけるトランジションの効果的選択法(コンカレントシステム, 離散事象システム, ハイブリッドシステム, 及び一般)
- ペトリネット発火系列探索法の動作的デッドロック回避に基づく改良(コンカレントシステム, 一般)
- 指定プレースをサポートに含むペトリネットインバリアントの線形計画法に基づく算出法(コンカレントシステム, 一般)
- 時間付きペトリネットの発火系列探索における発火禁止則の効果について(グラフ,ペトリ,ニューラルネット及び一般)
- 時間付きペトリネットの発火系列探索における発火禁止則の効果について(グラフ,ペトリ,ニューラルネット及び一般)
- ペトリネットのサイフォン・トラップに基づくインバリアント改良算出法(コンカレント工学理論と応用一般)
- トランジション発火禁止則に基づくペトリネットの発火系列探索法RADQ^*(コンカレント工学及びハイブリッドダイナミカルシステムの理論と応用,一般)
- ペトリネットのサイフォン・トラップに基づくインバリアント算出法(コンカレント工学及びハイブリッドダイナミカルシステムの理論と応用,一般)
- ペトリネットのサイフォン・トラップ抽出効率化のためのサブネット縮約法(グラフ,ペトリ,ニューラルネット,及び一般)
- ペトリネットのサイフォン・トラップ抽出効率化のためのサブネット縮約法(グラフ,ペトリ,ニューラルネット,及び一般)
- ペトリネットのサイフォン・トラップ抽出効率化のためのサブネット縮約法
- 時間付きペトリネットの発火遅延操作に基づく発火系列探索(コンカレント工学一般)
- ペトリネット最小初期マーキング問題に対する発見的解法AADの高速化(コンカレント工学一般)
- グラフの最大誘導木を抽出する発見的解法の点除去に基づく性能強化
- グラフの最大誘導木抽出法の計算機実験による性能評価(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- グラフの最大誘導木抽出法の計算機実験による性能評価(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 確率フローネットワークの頂点容量割り当て問題に対する発見的解法 (コンカレント工学)
- 発火系列探索法の改良に基づいて性能強化されたペトリネットマーキング構成問題解法 (コンカレント工学)
- 時間付きペトリネットにおける最小初期マーキング問題に対する発見的解法TPMとTMDLO(グラフ,ペトリネット,ニューラルネット及び一般)
- 時間付きペトリネットにおける最小初期マーキング問題に対する発見的解法TPMとTMDLO(グラフ,べトリネット,ニューラルネット及び一般)
- 次数制約付きのグラフに対する指定点3辺連結化問題の解法
- 次数制約付きのグラフに対する指定点3辺連結化問題の解法
- 次数制約付きのグラフに対する指定点k辺連結化について
- 平面的2辺連結化問題に対する解法の実験的評価
- グラフの格子描画に対するコンパクション手法のプリント基板設計への応用(グラフ,ペトリ,ニューラルネット及び一般)
- グラフの格子描画に対するコンパクション手法のプリント基板設計への応用(グラフ,ペトリ,ニューラルネット及び一般)
- グラフの格子描画に対するコンパクション手法のプリント基板設計への応用
- グラフ彩色問題に対するPCクラスタ並列分枝限定解法の性能強化(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- グラフ彩色問題に対するPCクラスタ並列分枝限定解法の性能強化(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- グラフ彩色問題に対するPCクラスタ並列分枝限定解法の性能強化(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- 階層型グラフに対応したグラフアルゴリズムの視覚的トレースツールの開発(グラフ,ペトリ,ニューラルネット及び一般)
- 階層型グラフに対応したグラフアルゴリズムの視覚的トレースツールの開発(グラフ,ペトリ,ニューラルネット及び一般)
- グラフ点彩色問題の分散分枝限定解法ParaBSCに対するVNSに基づく性能強化
- グラフ点彩色問題解法の性能強化
- いくつかのグラフ連結度関連問題に対する(2-2/(|V|))-近似アルゴリズム
- グラフの指定点集合2点連結化問題に対する近似アルゴリズムSPA
- 各種情報の収集・編集・表示機能を有する大学運営業務支援システムSUMOSYS(システム構築,ライフログ活用技術,オフィス情報システム,ライフインテリジェンス)
- カンファレンスに対するセッションスケジューリングシステムの開発(オフィス情報システム,ライフログ活用技術,オフィス情報システム,マルチメディアシステム,マルチメディア通信,IP放送/映像伝送,一般)
- Webシステムによる学生授業評価アンケートの実施方法とその検証 (ライフインテリジェンスとオフィス情報システム)
- 次数制約付きのグラフに対する指定点2点連結化問題の解法
- λ-辺連結グラフにおける指定点集合の(λ+1)-辺連結化のための2-近似アルゴリズムFSA+1
- カンファレンスに対するセッションスケジューリングシステムの開発
- グラフに対する最大供給分割問題解法の性能評価
- 広島大学生物圏科学研究科における教育記録システムの開発
- 制約付きビア数最小化問題に対する改良解法K-LAG-VおよびK-LAG-VL
- U-MOS:各種情報の収集・編集・表示機能を有する大学運営業務支援システム
- グラフの2点または3点連結化アルゴリズムの計算機実験に基づく性能評価
- カンファレンスプログラム編成のための局所探索法の改良
- 指定矩形形状を持つプリント基板設計のための回路2分割法(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- 指定矩形形状を持つプリント基板設計のための回路2分割法(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- 2層配線における制約付きビア数最小化手法の高速化と多層配線問題への応用
- AP-1-3 工学系数学基礎における到達目標と学力評価について : EMaTを例として(AP-1.回路基礎教育 : 何をどこまで,パネルセッション,ソサイエティ企画)