需要点と供給点のある木のコスト最小分割
スポンサーリンク
概要
- 論文の詳細を見る
与えられた木Tの各点は供給点または需要点であり,それぞれ供給量または需要量と呼ばれる正整数が割当てられている.Tの各々の需要点vに対し,vの需要量に等しいパワーを,Tの向き付けされた辺を通して,1個の供給点からvに供給したい.Tの各辺eには向きと正整数が割当てられていて,この正整数はTからeを除去するか,あるいはeの向きを逆向きにするのにかかるコストを表している.このとき,Tから辺を除去したり,辺の向きを逆にしたりして,次の条件(a)と(b)を満たすようにTをいくつかの部分木に分割したい.(a)各部分木には,ちょうど1個の供給点があり,その供給量はその部分木に含まれる全ての需要点の需要量の合計以上である.(b)各部分木は供給点を根とした根付き木であり,全ての辺は親から子へ向き付けされている.本論文では,与えられた木Tをこのような根付き部分木に分割するためにかかるコストを最小化する問題を扱う.この最小化問題がNP困難であることを示した上で,この問題を解く擬多項式時間アルゴリズムを与える.更に,この問題に対する多項式時間の完全近似スキーム(FPTAS)も与える.
- 社団法人電子情報通信学会の論文
- 2010-11-26
著者
-
周 暁
東北大学大学院情報科学研究科
-
西関 隆夫
東北大学大学院情報科学研究科
-
伊藤 健洋
東北大学大学院情報科学研究科
-
西関 隆夫
関西学院大学理工学部
-
原 拓哉
東北大学大学院情報科学研究科
-
西関 隆夫
関西学院大学理工学部情報科学科
-
伊藤 健洋
東北大学情報科学研究科
関連論文
- バランスのよいグラフ分割を用いた平面グラフの小面積格子描画法
- ブール剰余関数を計算するしきい値論理回路のサイズとエネルギー複雑度のトレードオフ
- 木の均一分割問題
- 3連結平面グラフの細分の格子凸描画
- 多値2入力論理関数のAND-EXOR論理式の最小化(理論,回路,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 需要点と供給点があるグラフの分割問題の近似可能性
- 内部三角化平面グラフの開矩形勢力描画
- 平面グラフの矩形外周格子凸描画
- 現在のWebにおけるHITSについて
- 平面グラフの外頂点数最小の凸描画
- 直並列グラフの折れ曲がり最小の直交描画
- グラフの距離辺彩色アルゴリズム
- 需要点と供給点のあるグラフの分割
- 鍵共有グラフのt-安全性について
- 平面グラフの内部矩形描画
- 需要と供給の木の分割
- 平面グラフで最短非交差道を求めるアルゴリズム
- 平面上で二組の端子対の間の長さの和が最小で辺素な道を求めるアルゴリズム
- 軸平行多角形障害物がある平面上の最短路
- 4つの端子からの距離の和が小さい領域を求めるアルゴリズム
- 障害物と交差領域のある平面上での最短な2本の道
- 平面領域で長さの総和最小な非交差道を求めるアルゴリズム
- 軸平行多角形障害物がある平面における最短路アルゴリズム
- 平面上で2本の最短な道を求めるアルゴリズム
- 3連結平面グラフの非分離耳分割を求める線形アルゴリズム
- 平面グラフで長さの総和最小な非交差道を求めるアルゴリズム
- Efficient Algorithms for Edge-Coloring Partial k-Trees
- A Parallel Algorithm for Drawing Planar Graphs on the Grid
- 3-連結グラフの3分割アルゴリズム
- 平面グラフで林を求めるアルゴリズム--指定された2つの面の両方にまたがるネットがある場合
- 平面グラフで内素な道を求めるアルゴリズム
- 平面グラフで林を求めるアルゴリズム--各ネットの端子が指定された2つの面の片方にある場合
- 可変優先キューとその応用(計算アルゴリズムの基礎理論)
- 入れ子状長方形格子グラフの辺素な道
- 入れ子状長方形領域で辺素な道を求めるアルゴリズム (ネットワ-ク問題論文)
- ある種の平面ネットワ-クに対する多種フロ-アルゴリズム
- 平面多種フロ-と最短路
- 平面的グラフの矩形描画
- 部分k-木で辺素な道をみつけるアルゴリズム
- 部分k木を全彩色する多項式時間アルゴリズム
- 最大カットセット及び2部グラフ化に関するNP-完全問題
- 平面グラフで長さの総和最小な非交差道を求めるアルゴリズム
- 3-連結グラフの3分割アルゴリズム
- 可変形状ラベリング問題に対するアルゴリズム
- 木の最小コスト辺彩色のマッチングへの帰着
- 一方向性落し戸環準同型に基づくメッセージ確認方式
- 非可換環上の多重署名についての考察
- 環準同型の性質をもつ暗号化関数の一構成
- 離散対数暗号系に付随する言語の複雑さについて
- 離散対数暗号に付随する言語の複雑さについて
- 平面多種フロ-アルゴリズム
- 平面グラフの多種フロ-を求める多項式時間アルゴリズム
- 平面3-グラフの折れ曲がり数最少な直交描画
- 3連結3次平面グラフを最小個のベンドを用いて直交描画する線形時間アルゴリズム
- 4連結平面グラフを4分割する線型時間アルゴリズム
- 多値2入力論理関数のAND-EXOR論理式の最小化(理論,回路,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 多値2入力論理関数のAND-EXOR論理式の最小化(理論,回路,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 平面グラフの面の面積を指定した8角形描画
- 対称関数を計算するユネイト回路のサイズとエネルギーのトレードオフ
- ブール剰余関数を計算するしきい値論理回路のサイズとエネルギー複雑度のトレードオフ
- A-026 グラフ分割を用いた格子描画法(モデル・アルゴリズム・プログラミング,一般論文)
- グラフの距離辺彩色アルゴリズム
- 直並列グラフの折れ曲がり最小の直交描画
- 2-連結グラフの2分割アルゴリズム
- 部分k木で辺素な道を見つけるアルゴリズム
- 木を辺ランク付けする効率のよいアルゴリズム
- 部分k木を[g,f]-辺彩色する多項式時間アルゴリズム
- 部分k-木に対する[g,f]-辺彩色アルゴリズム
- 部分κ木を辺彩色する並列アルゴリズム
- 部分$k$木を全彩色する線形時間アルゴリズム (新しいパラダイムとしてのアルゴリズム工学)
- DS-1-4 剰余関数を計算するしきい値回路のエネルギー複雑度とファンイン(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- LA-11 直並列グラフをリスト辺彩色するアルゴリズム(A. アルゴリズム・基礎)
- 直並列グラフをリスト辺彩色するアルゴリズム
- 部分k-木のl-点彩色多項式時間アルゴリズム
- 木の最小コスト辺彩色のマッチングへの帰着
- 需要点と供給点のある木のコスト最小分割
- 木のリスト辺彩色の遷移可能性
- A-37 直並列グラフのリスト全彩色(グラフアルゴリズム(1),A.アルゴリズム・基礎)
- 剰余関数を計算するエネルギー複雑度の小さいしきい値回路
- 退化的グラフの全彩色
- 部分k-木の全彩色を求める線形時間アルゴリズム
- 部分k-木の全彩色を求める多項式時間アルゴリズム
- 部分κ-木の一般化点ランキング
- 木の一般化辺ランキング
- 木の分割問題を解くアルゴリズム
- 直並列グラフの重み付き彩色の効率のよいアルゴリズム
- 部分k木で独立全域木を見つけるアルゴリズム
- 部分κ木に対する辺素な道問題のNP-完全性
- 部分k-木をf-辺彩色するアルゴリズム
- グラフの辺彩色及びƒ-辺彩色アルゴリズム
- 木,カクタスにおける点被覆の遷移可能性
- グラフの帯域幅連続多重彩色を求めるアルゴリズム
- DS-1-9 グラフのL(2,1)ラベリングの遷移可能性(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- グラフ上の拡散競争ゲームの計算複雑さ
- 論理回路の出力パターン数え上げ
- グラフの帯域幅連続多重彩色を求めるアルゴリズム
- 関数$P^n_D$を計算するしきい値回路 (理論計算機科学の新展開)
- Energy-Efficient Threshold Circuits Detecting Global Pattern in 1-Dimensional Arrays (New Trends in Theoretical Computer Science)
- グラフのリストL(2,1)ラベリングの遷移可能性(一般)
- 論理回路の出力パターン数え上げ(一般)