無向グラフ上の辺分離問題を解く簡単なO(mn)時間アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
偶数次数の指定された点sを持つk-辺連結無向多重グラフG=(V,E)が与えられたとき, sに接続する2辺(s,u),(u,υ)を1辺(u,υ)に置き換える操作を反復し(グラフのk-辺連結性を保ちながら) sを孤立点化させる問題を考える。最近、n=|V|, mをGにおいて辺の張られている点対の数としたとき、この問題を解くO(n(m+nlog n)log n)時間のアルゴリズムが開発されたが[H. Nagamochi and T. Ibaraki, Deterministic O(nm) time edge-splitting in undirected graphs, Proceedings 28th ACM Symposium on Theory of Computing,1996, pp.64-73]、このアルゴリズムはやや複雑である。本報告では、同じO(n(m+nlog n)log n)の計算時間を持つより簡単なアルゴリズムを提案する。
- 1996-10-17
著者
関連論文
- 給油施設操業スケジューリング (企業事例)
- 特集にあたって (ユーザのための数理計画応用)
- 多次元直方体被覆問題および充足可能性問題を解くアルゴリズム
- 緩和法による演繹データベースの問合せ評価
- 多変数同世代問題に対する問い合わせ評価法
- 多変数同世代問題に対する問合せ評価法
- 緩和法による演繹データベースの問い合わせ評価
- 多変数線形再帰型演繹データベースに対する逆数え上げ評価法
- 自己双対正論理関数の分解について
- 格子型光波網におけるパス割り当て問題に関する考察
- Serializable Classesの構造について(計算機構に関する数学的基礎理論とその応用)
- 先読みスケジューラによる分散型データベースシステムの並行処理制御(計算アルゴリズムと計算量の基礎理論)
- 版数制限をもつ先読みスケジュ-ラ
- グラフパッキング問題の計算複雑度(計算機科学の基礎理論とその応用)
- 内点法
- ランダム有向グラフにおける到達可能性と推移閉包の大きさについて
- 関係の推移閉包の大きさの近似的推定法
- 演えきデータベースにおける質問処理コストの近似的評価法
- Complexity of the Optimum Join Order Problem in Deductive Databases
- 辺連結度増加関数をO^^〜(mn)時間で計算するアルゴリズム
- 最終ダブルオファー仲裁の均衡戦略について
- フローゲームの凸性について(ゲーム理論(2))
- 最終ダブルオファー仲裁(FDOA)の均衡戦略の解析について(ゲーム理論(1))
- マトロイド上の最小基ゲーム
- 多次元コスト関数をもつ有限オートマトンについて (情報科学の数学的基礎理論と応用)
- ある種の平面有向ネットワークの多品種流問題について(計算アルゴリズムと計算量の基礎理論)
- タブー探索による直交ラテン方陣の構成(連続と離散の最適化数理)
- 中間経由節点をもつKサーバー問題(計算機構とアルゴリズム)
- 最小容量カットアルゴリズムのプログラムによる効率の良い実現法
- 多重グラフにおける(λ+1)-カット
- 領域制約の下でのゲーム木探索(計算アルゴリズムと計算量の基礎理論)
- ゲーム木探索法SSSの非劣性について(計算アルゴリズムの基礎理論)
- 無向グラフ上の辺分離問題を解く簡単なO(mn)時間アルゴリズム
- 高信頼性ユニットからなる並-直列システムの漸近的に最適な保全政策(信頼性)
- 経済状態を考慮したアメリカンオプションの最適行使問題(ポートフォリオ)
- 33. 線形計画問題の高速解法 (アルゴリズムの最近の動向)
- Learning Algorithms for 2 × 2 Stochastic Games with Incomplete Information
- グラフ上の搬送スケジューリング問題の計算の複雑さについて(スケジューリング(2))
- グラフ上の搬送スケジューリング問題の計算の複雑さについて
- 遺伝アルゴリズムにおける交叉法に対する一考察(計算量理論)
- 1機械スケジューリング問題に対するSSDP法(動的計画法)
- 部分定義論理関数の正論理関数とHorn関数における関数分解について
- サブツアー交換交叉に対する二つのコメント
- サブツアー交換交叉に対する2つのコメント
- 不完全例題に対するプール的解析
- 鎖パッキング問題について(アルゴリズムの数学的基礎理論とその応用)
- ジャンケンのトーナメント表現と意味のある拡張(アルゴリズムと計算量理論)
- T-混合カットにおける領域間連結度の性質(グラフ・ネットワーク(5))
- 最小カット問題の簡潔かつ構成的な証明
- 平面グラフにおける辺遊離操作と辺連結度増大問題について
- Primal-Dual Proximal Point Algorithm for Multicommodity Network Flow Problems(MATHEMATICAL OPTIMIZATION AND ITS APPLICATIONS)
- 非線形最小費用流問題に対する双対ニュートン法(決定理論とその周辺)
- 年齢に依存した費用を持つ小修理・取替え問題についてII(信頼性)
- 年齢に依存した費用を持つ小修理・取替え問題について(信頼性)
- 平均費用規範最適小修理・取替え問題について(最適化理論とその関連分野)
- ある信頼性システムに対する修理限界取替え政策の最適性について(マルコフ解析)
- 平均費用規範最適小修理・取替え問題について(マルコフ解析)
- 多項過程モデルによるルックバックオプションの価格の上・下界評価(数理計画モデルにおける最適化理論)
- 多項過程モデルによるルックバックオプションの価格の上・下界評価(金融)
- 組合せ最適化ゲーム
- 反復ラインダイグラフの深さの浅い独立全域木
- 資産の収益率の相関がある構造を持つポートフォリオ選択問題について(資金・資本の流れ)
- ポートフォリオ選択問題における投資家の危険回避性と初期の富の影響(ポートフォリオ)
- ポートフォリオ選択問題における資産の収益率の確立順序(最適化の数理とその応用)
- グラフのサム数に対する上下界について
- 多期間ポートフォリオ選択問題における分離定理(計画数学とその関連分野)
- リーダー選出問題における時間最小アルゴリズムについて(計算アルゴリズムと計算量の基礎理論)
- 格子型光波ネットワークの再構成アルゴリズムについて
- 光波ネットワークのノード再配置アルゴリズムについて
- 双方向マンハッタン・ストリート・ネットワークの網再構成について
- データの論理的解析とブール関数
- データの論理的解析とブール関数
- 部分定義論理関数の内核関数と外核関数
- 2-単調正論理関数の同定問題に対する単純な高速アルゴリズム
- 論理関数の内包関数と外包関数について
- 不完全に定義された正論理関数の最大潜伏度について
- 正論理関数の最大潜伏度について(計算機構とアルゴリズム)
- 大規模非線形計画問題に対する逐次2次計画分解法