グラフの最小コスト3-点連結化問題に対する近似アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
本稿では以下のように定義される,グラフの最小コスト3-点連結化問題(W-3-VCA)に対する3つの近似アルゴリズムMCM,SMC,MCFを実験的に比較評価する:"完全グラフG=(V,E),その生成部分グラフG_0=(V,E')と枝e∈Eに対する非負整数のコストc(e)(但し,e'∈E'ならばc(e')=0,e"∈E-E'ならばc(e")〉0)が与えられたとき,G_0を3-点連結にするようなコスト総和が最小となる付加辺集合を求めよ".これらの実験結果によれば,一般に最大コストマッチングを求めることを基本とするMCMが最もよい性能を持つことが示された.
- 社団法人電子情報通信学会の論文
- 1994-01-26
著者
-
間島 利也
広島国際大学工学部
-
田岡 智志
広島大学大学院工学研究科
-
渡辺 敏正
広島大学工学部
-
田岡 智志
広島大学工学部第二類回路・システム工学講座
-
間島 利也
広島国際大学 社会環境科学部 情報通信学科
-
間島 利也
広島大学工学部第二類回路システム工学講座
-
川合 宏之
広島大学工学部第二類回路システム
関連論文
- 点次数の増加上限制約を持つ2点連結グラフに対する線形時間3点連結化アルゴリズム
- カンファレンスに対するセッションスケジューリングシステムの開発(ライフログ活用技術,オフィス情報システム,マルチメディアシステム,マルチメディア通信,IP放送/映像伝送,一般)
- カンファレンスに対するセッションスケジューリングシステムの開発(オフィス情報システム,ライフログ活用技術,オフィス情報システム,マルチメディアシステム,マルチメディア通信,IP放送/映像伝送,一般)
- Web-GISに基づく不動産ナビゲーションシステム"賀茂ナビ" : 情報管理機能とインターフェースの改良(オフィスインフォメーションシステム,ディジタルドキュメント、一般)
- メタWebシステム"GECOD'の開発に関する報告 : 生成されるWebシステムの認証機能・権限付与と基礎的機能について(システム構築,ライフログ活用技術,オフィス情報システム,ライフインテリジェンス)
- グラフの最大誘導木を抽出する発見的解法の点除去に基づく性能強化
- 辺重み付きカクタスにおけるネット分割に基づく発火系列探索(コンカレント工学及びハイブリッドダイナミカルシステムの理論と応用,一般)
- 各トランジションの発火が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法の安定性向上(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- ペトリネットマーキング構成問題に対する発火系列探索法の改良(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- A-12-4 トランジション改良選択法に基づくペトリネット最小初期マーキングの効率的構成法(A-12.コンカレント工学,一般講演)
- 指定プレースをサポートに含む極小サポートインバリアントのサイフォン・トラップに基づく算出法(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- ペトリネットの最小初期マーキング探索におけるトランジションの効果的選択法(コンカレントシステム, 一般)
- ペトリネットの最小初期マーキングのための動作的デッドロック回避に基づく高速な発見的解法(コンカレントシステム, 離散事象システム, ハイブリッドシステム, 及び一般)
- ペトリネットの発火系列探索におけるトランジションの効果的選択法(コンカレントシステム, 離散事象システム, ハイブリッドシステム, 及び一般)
- ペトリネット発火系列探索法の動作的デッドロック回避に基づく改良(コンカレントシステム, 一般)
- 指定プレースをサポートに含むペトリネットインバリアントの線形計画法に基づく算出法(コンカレントシステム, 一般)
- 時間付きペトリネットの発火系列探索における発火禁止則の効果について(グラフ,ペトリ,ニューラルネット及び一般)
- 時間付きペトリネットの発火系列探索における発火禁止則の効果について(グラフ,ペトリ,ニューラルネット及び一般)
- ペトリネットのサイフォン・トラップに基づくインバリアント改良算出法(コンカレント工学理論と応用一般)
- トランジション発火禁止則に基づくペトリネットの発火系列探索法RADQ^*(コンカレント工学及びハイブリッドダイナミカルシステムの理論と応用,一般)
- ペトリネットのサイフォン・トラップに基づくインバリアント算出法(コンカレント工学及びハイブリッドダイナミカルシステムの理論と応用,一般)
- 時間付きペトリネットの発火遅延操作に基づく発火系列探索(コンカレント工学一般)
- ペトリネット最小初期マーキング問題に対する発見的解法AADの高速化(コンカレント工学一般)
- グラフの最大誘導木を抽出する発見的解法の点除去に基づく性能強化
- AP-1-5 トピックと著者情報に基づく学術会議プログラム自動編成法(AP-1.アカデミックカンファレンスマネジメントシステムのあるべき姿,パネルセッション,ソサイエティ企画)
- AP-1-3 学術会議運営支援Webシステム : オールワンサービスへの試み(AP-1.アカデミックカンファレンスマネジメントシステムのあるべき姿,パネルセッション,ソサイエティ企画)
- 時間付きペトリネットにおける最小初期マーキング問題に対する発見的解法TPMとTMDLO(グラフ,ペトリネット,ニューラルネット及び一般)
- 時間付きペトリネットにおける最小初期マーキング問題に対する発見的解法TPMとTMDLO(グラフ,べトリネット,ニューラルネット及び一般)
- 次数制約付きのグラフに対する指定点3辺連結化問題の解法
- 次数制約付きのグラフに対する指定点3辺連結化問題の解法
- 次数制約付きのグラフに対する指定点k辺連結化について
- 次数増加禁止点を持つグラフの指定点3辺連結化問題に対する線形時間アルゴリズム
- 次数増加禁止点を持つグラフの指定点3点連結化問題に対する線形時間アルゴリズム
- 次数増加禁止点を持つグラフの指定点集合に対する2, 3点連結化問題の解法
- 次数増加禁止点を持つグラフに対する点連結度増加問題
- 次数増加禁止点を持つグラフに対する点連結度増加問題
- グラフの指定点集合に対する3点連結化問題の解法
- グラフの指定点3点連結化問題に対する解法
- グラフの局所辺連結度増加問題に対する近似解法
- グラフのk辺連結化問題に対する新しい近似解法
- 平面的2辺連結化問題に対する解法の実験的評価
- グラフの格子描画に対するコンパクション手法のプリント基板設計への応用(グラフ,ペトリ,ニューラルネット及び一般)
- グラフの格子描画に対するコンパクション手法のプリント基板設計への応用(グラフ,ペトリ,ニューラルネット及び一般)
- グラフの格子描画に対するコンパクション手法のプリント基板設計への応用
- グラフ彩色問題に対するPCクラスタ並列分枝限定解法の性能強化(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- グラフ彩色問題に対するPCクラスタ並列分枝限定解法の性能強化(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- グラフ彩色問題に対するPCクラスタ並列分枝限定解法の性能強化(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- A-12-4 指定プレース集合を含むサポートを持つペトリネットインバリアントの算出法
- 指定ノード集合を含むサポートを持つペトリネットインバリアントの算出アルゴリズムFMSN
- 指定ノード集合を含むサポートを持つペトリネットインバリアントの算出アルゴリズムFMSN
- グラフ点彩色問題の分散分枝限定解法ParaBSCに対するVNSに基づく性能強化
- グラフ点彩色問題解法の性能強化
- グラフ点彩色問題解法の性能強化とその応用 (第21回 回路とシステム軽井沢ワークショップ論文集) -- (グラフアルゴリズム)
- いくつかのグラフ連結度関連問題に対する(2-2/(|V|))-近似アルゴリズム
- グラフの指定点集合2点連結化問題に対する近似アルゴリズムSPA
- 各種情報の収集・編集・表示機能を有する大学運営業務支援システムSUMOSYS(システム構築,ライフログ活用技術,オフィス情報システム,ライフインテリジェンス)
- カンファレンスに対するセッションスケジューリングシステムの開発(オフィス情報システム,ライフログ活用技術,オフィス情報システム,マルチメディアシステム,マルチメディア通信,IP放送/映像伝送,一般)
- 次数制約付きのグラフに対する指定点2点連結化問題の解法
- λ-辺連結グラフにおける指定点集合の(λ+1)-辺連結化のための2-近似アルゴリズムFSA+1
- グラフの最小コスト3-点連結化問題に対する近似アルゴリズム
- カンファレンスに対するセッションスケジューリングシステムの開発
- グラフに対する最大供給分割問題解法の性能評価
- 広島大学生物圏科学研究科における教育記録システムの開発
- 制約付きビア数最小化問題に対する改良解法K-LAG-VおよびK-LAG-VL
- U-MOS:各種情報の収集・編集・表示機能を有する大学運営業務支援システム
- ペトリネットのサイフォン・トラップサポート集合に基づくインバリアント算出法
- 指定ノード集合を含むサポートを持つペトリネットインバリアントの算出アルゴリズム FMSN
- CONTEC : 辺交差の制御機能を有するグラフ描画システム
- グラフの2点または3点連結化アルゴリズムの計算機実験に基づく性能評価
- カンファレンスプログラム編成のための局所探索法の改良
- 指定矩形形状を持つプリント基板設計のための回路2分割法(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- 指定矩形形状を持つプリント基板設計のための回路2分割法(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- ペトリネット発火系列問題のデッドロック成分回避操作に基づく発見的解法FSDC
- ペトリネット初期マーキング最小化のための改良発見的アルゴリズムAAD
- ペトリネット初期マーキング最小化のための改良発見的アルゴリズムAAD
- CST2000-9 ペトリネットの最小初期マーキング問題に対する発見的アルゴリズムFMDB