全域木詰め込みに基づいたハイパーグラフ分割
スポンサーリンク
概要
- 論文の詳細を見る
いくつかの辺を取り除くことによってハイパーグラフがk個の連結成分に分割されるとき,その辺の集合はハイパーグラフのk分割カットと呼ばれる.グラフの最小容量k分割カットはkが定数であるとき多項式時間で計算できるのに対し,ハイパーグラフの最小容量k分割カットはkが定数であっても多項式時間で計算できるかどうかは分かっていない.本報告では,kとハイパーグラフのランクの両方が定数であるときにハイパーグラフの最小容量k分割カットを強多項式時間で求めるアルゴリズムを与える.我々のアルゴリズムは,貪欲法で構築した全域木詰め込みからグラフの最小容量k分割カットを計算するThorup (2008)のアルゴリズムを拡張したものとなっている.
- 2010-04-15
著者
関連論文
- 劣モジュラシステム分割問題に対するアルゴリズム
- Support Vector Machineにおけるルールの利用(線形計画)
- 無向グラフにおける集合連結問題
- 辺連結度制約と次数制約をもつネットワーク設計問題
- 全域木詰め込みに基づいたハイパーグラフ分割
- 組合せの効率的な生成法 (計算機科学とアルゴリズムの数理的基礎とその応用)
- 長さに上限をもつパスによる有向グラフの被覆に対するアルゴリズム
- 局所点連結制約を持つ供給点配置問題に対する近似アルゴリズム
- 局所辺連結度を保存するオイラーグラフ節点分離
- 重み付き次数制約を持つネットワーク設計問題
- 1-D-1 Algorithms for Covering Digraphs by Length-Bounded Walks