辺付加による(σ+1)-辺連結単純グラフ構成のための効率的アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
k辺連結化問題とは、与えられた無向グラフG=(V, E)に付加して得られるグラフG′=(V, E∪E′)がk辺連結となるような最小辺集合E′を求める問題である。本稿では、"辺付加により新たに多重辺を作らない"、という条件を加えたk辺連結化問題を扱う。一般には、この問題はNP-hardであり、Gの葉と呼ばれる点集合の総数により問題の難しさが変わることが知られている。本稿では、Gが辺連結度σの単純グラフで、k=σ+1である場合の解法として、既存手法を次の2点で改良した手法を提案する : 計算時間をO(σ^2|V|log(|V|/σ)+|E|)に改善し、かつ、多項式時間で解ける範囲が、リーフグラフの最大マッチングMが|M|≥⌊σ/2⌋+α(αはある定数)である場合に拡大した。
- 一般社団法人電子情報通信学会の論文
- 2000-11-02
著者
関連論文
- 点次数の増加上限制約を持つ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(グラフ,べトリネット,ニューラルネット及び一般)
- 平面的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
- 指定矩形形状を持つプリント基板設計のための回路2分割法(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- 動的最短経路問題アルゴリズムの性能比較(グラフ, ペトリ, ニューラルネット及び一般)
- Web-GISに基づく不動産ナビゲーションシステム"賀茂ナビ"(オフィスインフォメーションシステム及び一般)
- サイクリックカクタスに対する発火系列問題の解法について
- 広島大学生物圏科学研究科における教育記録システムの開発 (メディア工学)
- SA-6-8 通信ネットワーク3辺連結化のための分散アルゴリズム
- 通信ネットワークの(σ+1)辺連結化問題に対する効率的分散アルゴリズムDECA-1
- 通信ネットワークの(σ+1)辺連結化問題に対する効率的分散アルゴリズムDECA-1
- 確率フローネットワークの頂点容量割り当て問題に対する発見的解法(一般,コンカレントシステム及び一般)
- 需要-供給グラフに対する最大供給分割問題解法の性能評価
- 発火系列探索法の改良に基づいて性能強化されたペトリネットマーキング構成問題解法(一般,コンカレントシステム及び一般)
- ペトリネットの極小サイフォン・トラップ抽出アルゴリズムとそのP-インバリアント計算への応用