需要点,供給点,辺容量を持つ木の分割アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
木Tの点は供給点あるいは需要点であるとし,各供給点には供給量と呼ばれる正の数が割り当てられ,各需要点には需要量と呼ばれる正の数が割り当てられているとする.また,各辺には正の数である容量が割り当てられているとする.Tから辺を除去することによって,Tをいくつかの部分木に分割し,各部分木はちょうど1つの供給点を持ち,その供給量がその部分木の需要量の合計以上であり,しかも各辺を流れるフローが辺容量以下であるようにしたい.分割問題とはTにこのような分割が存在するか判定する問題であり,最大分割問題とは分割問題の最大化版である.本文ではこれらの問題に対して3つのアルゴリズムを与える.1つ目は分割問題を線形時間で解くアルゴリズムである.2つ目は最大分割問題を擬多項式時間で解くアルゴリズムである.3つ目は最大分割問題を解くFPTAS(Fully Polynomial-Time Approximation Scheme)である.
- 2011-06-23
著者
関連論文
- 木の最小コスト辺彩色のマッチングへの帰着
- 木の最小コスト辺彩色のマッチングへの帰着
- 需要点と供給点のある木のコスト最小分割
- 内部3連結グラフの格子凸描画
- 鍵共有グラフを用いた絶対に安全なメッセージ送信
- 需要点,供給点,辺容量を持つ木の分割アルゴリズム
- 内部3連結グラフの格子凸描画(情報・システム基礎,学生論文)
- グラフの帯域幅連続多重彩色を求めるアルゴリズム
- グラフの帯域幅連続多重彩色を求めるアルゴリズム
- 帯域幅連続多重彩色の近似アルゴリズム(一般)