直並列グラフの全域配送木
8
0
0
全文
(2) Vol.2013-AL-143 No.10 2013/3/1. 情報処理学会研究報告 IPSJ SIG Technical Report. 3. 9 (6). 8 (3). 8 15 30 (5) (12) 11 (5) 12 (12) 7 10. 1. 5. 3. 4. (8). 15 (2). 3 図 1. 2. 15. 1. 7 (7). 5. 11 (5). 2. 図 3. 直並列グラフ. 直並列グラフ G とその全域配送木 T. 0. 0. (a) ・ ・ ・. 図 4 全域配送木問題への多項式時間帰着. (b). 端子 と呼ばれる．. 2. 図 2(b) のような端子 s1 ，t1 を持つ直並列グラフ G1 と 端子 s2 ，t2 を持つ直並列グラフ G2 を次のように接続 して得られるグラフ G は直並列グラフである． (c). (a) 図 2(c) のように t1 と s2 を同一視して得られるグラ フ G．ただし，G の端子は s = s1 と t = t2 である． この接続を 直列接続 と呼ぶ．. (b) 図 2(d) のように s1 と s2 を同一視し，t1 と t2 を 同一視して得られるグラフ G．ただし G の端子は. s = s1 = s2 と t = t1 = t2 である．この接続を (d) 図 2. 直並列グラフの定義. 並列接続 と呼ぶ． 図 1 および 3 のグラフは直並列グラフである． 本節では全域配送木問題は直並列グラフに対してすら. 全域配送木問題は辺素道問題とも似てはいるが，道フロー. NP 完全であることを示す．全域配送木問題は明らかに. が全域木を誘導しなければならない点が異なる．. NP に属するので，既に NP 完全な問題として知られてい. 本文では，まず全域配送木問題は直並列グラフに対して. る集合分割問題 [4], p.47，が直並列グラフの全域配送木問. すら NP 完全である数少ない問題であることを示す．次に. 題に多項式時間で帰着できることを示せばよい．ここで. 直並列グラフの全域配送木問題を解く擬多項式時間アルゴ. 集合分割問題 とは，与えられた n 個の正整数 d1 , d2 , · · · , dn. リズムを与える．与えられた直並列グラフ G の点数を n. からなる集合 A を２つの部分集合 A1 と A2 に分割し，集. とし，需要量の総和を D とすると，本文のアルゴリズムの. 合 A1 内の整数の和が A2 内の整数の和と等しくなるよう. 4. 計算時間は O(D n) である．したがって，D が定数ならば. にできるかどうかを判定する問題である．この集合分割問. 線形時間で，D が n の多項式ならば多項式時間で走る．. 題の問題例 A = {d1 , d2 , · · · , dn } から直並列グラフ G を図. 2. 直並列グラフの全域配送木問題の NP 完 全性 直並列グラフ は次のように再帰的に定義される [13]．. 1. 図 2(a) のように１つの辺 (s, t) からなるグラフ G は直 並列グラフである．その辺の両端点 s, t はグラフ G の ⓒ 2013 Information Processing Society of Japan. 4 のように構成する．G には 1 個のソース w と n + 2 個 ∑n のシンクがある．w の供給量 sup(w) は i=1 di であると する．また，整数 d1 , d2 , · · · , dn の各々を需要量をとする n 個のシンクと需要量 0 の 2 個のシンク s と t が G にある． ∑n 点 s や t とソース w とを容量 i=1 di /2 の辺で結ぶ．さら に 1 ≤ i ≤ n なる各 i について需要量 di のシンクを点 s や. 2.
(3) Vol.2013-AL-143 No.10 2013/3/1. 情報処理学会研究報告 IPSJ SIG Technical Report. P. P. S. S. S. S. S. P. 図 6. S. S. 直並列グラフ G の全域配送木. もある．一方，林 Fu′ は２本の木からなる林であり，Gu′ の全域二木である．本文のアルゴリズムは，G の二分分解 木 TBD の葉から根に向かって動的計画法を適用し，この ような全域配送木あるいは “全域配送二木”を求めていく．. 図 5 図 3 の直並列グラフの二分分解木 TBD. グラフ G には丁度 2 個のソース w1 と w2 があり，それ らの供給量を sup(w1 )，sup(w2 ) とする．G の全域部分グ. t と容量 di の辺で結ぶ．こうして得られた直並列グラフが. ラフ F が 全域配送二木 と呼ばれるのは，F が 2 本の点素. G である．明らかに分割問題に解があるとき，かつその時. な木 T1 ，T2 からなり，i = 1 および 2 について次の（a）お. に限り G に全域配送木が存在する．このようにして次の定. よび（b）が成立するときである．. (a) 木 Ti はソース wi を含み，Ti 内の需要量の合計は. 理が得られる． 定理 1. 全域配送木問題は直並列グラフに対してすら. sup(wi ) 以下である． (b) ソース wi から Ti の各点 v へ dem(v) だけのフローを. NP 完全である． このようにして，P ̸= NP ならば，直並列グラフの全域 配送木問題を多項式時間で解くアルゴリズムは存在しない．. 3. 擬多項式時間アルゴリズム. 木 Ti 上の wi から v へ行く道に沿って流したときに，. Ti の各辺 e のフローの値は cap(e) 以下である． 具体的には全域配送木や全域配送二木そのものではな く，それらが存在するかどうかを表現する６つの関数を計. 本節では，直並列グラフ G の全域配送木問題を解く擬. 算する．Gu がソース w を含むとき，Gu の全域配送木ある. 多項式時間アルゴリズムを与える. n をグラフの点数とし，. いは全域配送二木は Gu の端子からフローを出力できる．. 需要量の合計を D とすると，そのアルゴリズムの計算時間. 一方，Gu がソース w を含まないとき，端子からフローを. 4. 入力してもらわないといけない．こうした出力量と入力量. は O(D n) である．. x, y を変数とする 6 個の関数 fs,t , fst , fts , gts , gst , g s,t を各 3.1 直並列グラフの 2 分分解木とアルゴリズムの概要 直並列グラフ G は二分分解木 TBD により表現すること. 部分グラフ Gu に対して定義して，動的計画法により直並 列グラフの二分分解木 TBD の葉から根に向けてこれら 6. ができる．図 3 の直並列グラフの二分分解木を図 5 に示. 個の関数を計算する．関数名 f や g の下添字は出力端子名. す．TBD の各点 u は G の部分グラフ Gu に対応する．u が. を，上添字は入力端子名を表している．. TBD の葉ならば，Gu は G の１本の辺から誘導される部分 グラフである．TBD の内点 u に付けられたラベルs，pは. 3.2 関数の定義. それぞれ直列接続と並列接続を表している．u が TBD の. 需要量の合計 D は sup(w) 以下であるとしてよい．むろ. 内点であり，その子が u1 と u2 であり，u のラベルがs（あ. ん，どの辺を流れるフローも D 以下である．0 ≤ z ≤ D. るいはp）ならば，Gu1 と Gu2 を直列接続（あるいは並列. なる全ての整数 z からなる集合を ZD と書く．各部分グラ. 接続）して得られたグラフが Gu である．なお，直並列グ. フ Gu に関して定義される 6 個の関数の変数 x, y ∈ ZD は，. ラフの二分分解木は線形時間で構成できる [13]．. 各々端子 s および t からのフローの入出力量を表す．一方，. 本文のアルゴリズムは二分分解木に基づいた動的計画法. 関数の値は１または０であり，Gu に全域配送木や全域配. を利用する．直並列グラフ G の二分分解木 TBD の内点を. 送二木が存在するかどうかを表す．詳しくは次のように定. ′. ′. u, u とし，図 6 のように u, u に対応するグラフ G の部分. 義される．なお fs,t , fst , fts はソース w を含むグラフ Gu. グラフをそれぞれ Gu , Gu′ とすると，G の任意の全域配送. に対して定義されて，gts , gst , g s,t はソース w を含まないグ. 木 T はグラフ Gu , Gu′ の林 Fu , Fu′ を誘導する．図 6 で T. ラフ Gu に対して定義される．. は太線で描かれている．この例では，林 Fu は木であり，. (i) fs,t (Gu , x, y). ソース w は Gu に含まれており，Fu は Gu の全域配送木で ⓒ 2013 Information Processing Society of Japan. 図 7(a) のように Gu にはソース w が含まれるとし，Gu. 3.
(4) Vol.2013-AL-143 No.10 2013/3/1. 情報処理学会研究報告 IPSJ SIG Technical Report. (a) グラフ Gu. (a) グラフ Gu. (b)fs,t のグラフ G′u. (b)gts のグラフ G′u. (c)fst のグラフ G′u. (c)gst のグラフ G′u. (d)fts のグラフ G′u. (d)g s,t のグラフ G′u. 図 7. 図 8. fs,t ，fst ，fts の説明図. の端子を s, t とする．図 7(b) のように，Gu に仮のシンク ′. ′. gts ，gst ，g s,t の説明図. シンク t′ を付け加え，端子 t と容量が ∞ の辺で結ぶ．ま. s と t を付加し，それらの需要量を各々 x, y ∈ ZD とし，. た供給量が x の仮のソース s′ を付け加え，容量 ∞ の辺で. 各々 Gu の端子 s, t と辺で結び，それら２本の辺の容量を. 端子 s と結ぶ．こうして得られたグラフ G′u の全域配送二. ∞ とする．こうして得られた（直並列）グラフ G′u に全域. 木で，一つの木が点 s, s′ を含み，もう一つの木が点 w, t, t′. 配送木 T が存在するならば，fs,t (Gu , x, y) = 1 であり，存. を含むものが存在するならば，fts (Gu , x, y) = 1 であり，存. 在しないならば fs,t (Gu , x, y) = 0 であると関数 fs,t を定義. 在しないならば fts (Gu , x, y) = 0 であると fts を定義する．. する．直感的に言えば，fs,t (Gu , x, y) = 1 は，Gu の端子. (iv) gts (Gu , x, y). s および t からフローを各々 x および y だけ出力できる全. 図 8(a) のように Gu にソース w はないとする．図 8(b). 域配送木が Gu に存在することを意味する．なお，x ∈ / ZD. のように，Gu に仮のソース s′ とシンク t′ を付加し，s′ の. あるいは y ∈ / ZD のときには，便宜上 fs,t (Gu , x, y) = 0 と. 供給量を x とし，t′ の需要量を y とする．s′ と t′ の各々を. 定義する．他の５つの関数も同様である．. Gu の端子 s, t と辺で結び，それらの容量を ∞ とする．こ うして得られたグラフ G′u に全域配送木が存在するならば，. (ii) fst (Gu , x, y) ′. 図 7(c) のように，Gu に需要量が x の仮のシンク s を. gts (Gu , x, y) = 1 であり，存在しないならば gts (Gu , x, y) = 0. 付け加え，端子 s と容量 ∞ の辺で結ぶ．また供給量が y. であると gts を定義する．直感的に言えば，gts (Gu , x, y) = 1. の仮のソース t′ を付け加え，容量 ∞ の辺で端子 t と結ぶ．. は，端子 s からフローを x だけ入力されれば，端子 t から. こうして得られたグラフを G′u とすると，G′u にはソース. y だけ出力できるような配送全域木が Gu にあることを意. が2. 個ある．G′u. の全域配送二木で，一つの木が点 w, s, s. ′. ′. を含み，もう一つの木が点 t, t を含むようなものが存在 するならば，fst (Gu , x, y) = 1 であり，存在しないならば. fst (Gu , x, y) = 0 であると関数 fst を定義する．直感的に言 えば，fst (Gu , x, y) = 1 は，端子 t からフローを y だけ入力 されれば端子 s から x だけ出力できるような Gu の全域配 送二木が存在することを意味する．. (iii). fts (Gu , x, a, b). 味する．. (v) gst (Gu , x, y) 図 8(c) のように，gts の端子 s と t の役割を交換したもの が gst である．. (vi) g s,t (Gu , x, y) 図 8(d) のように，Gu に仮のソース s′ と t′ を付加し，そ れらの供給量を x と y とし，それぞれ端子 s と t と容量. ∞ の辺で結ぶ．こうして得られたグラフ G′u に，点 s′ と s. fst の定義で端子 s と t の役割を交換したものが fts であ. を含む木と点 t′ と t を含む木からなる全域配送二木が存在. る．詳しくは，図 7(d) のように，Gu に需要量が y の仮の. するならば，g s,t (Gu , x, y) = 1 であり，存在しないならば. ⓒ 2013 Information Processing Society of Japan. 4.
(5) Vol.2013-AL-143 No.10 2013/3/1. 情報処理学会研究報告 IPSJ SIG Technical Report. g s,t (Gu , x, y) = 0 であると g s,t を定義する．直感的に言え. （i）まず fs,t (G∗u , x, y) の計算方法を示す．G∗u にソース. (Gu , x, y) = 1 は，端子 s からフローを x だけ入力. w が含まれていて，w は G∗u の端子 s, t ではないとしてよ. され，端子 t から y だけ入力されれば，Gu に全域配送二. い．w は G1 に含まれるとしよう．（w が G2 に含まれる場. 木が存在することを意味する．. 合も同様である．）関数 fs,t (G∗u , x, y) を定義するときのグ. ば，g. s,t. ラフ G∗u ′ の全域配送木を T とすると，むろん T には閉路 がないので，T のフローのパターンはある整数 a, b ∈ ZD. 3.3 アルゴリズム グラフ Gu の端子 s や t はソース w であるかもしれない. に対して次の３つの場合がある．. し，需要量が正のシンクであるかもしれないが，どちらも. (a) 図 9(a) のように，G1 の外に端子 s と t から各々 x + a. 需要量が 0 であるシンクであるとした仮想的グラフを G∗u. と y + b だけフローが出力する．また，G2 の中に端子. と書くことにする．記述の便宜上，本文のアルゴリズムは. s と t から各々 a と b だけフローが入力される．. 二分分解木 TBD の葉から根に向かって，この仮想的グラ. (b) 図 9(b) のように，G1 の外に端子 s から x + a だけフ. フ. G∗u. に対して 6 つの関数を計算する．なお. G∗u. に対する. ローが出力し，G1 の中に端子 t から b だけ入力する． また，G2 には端子 s から a だけ入力し，端子 t から. 関数から Gu に関する関数は容易に計算できる． （a）全域配送木の存在判定方法. y + b だけフローが出力する．. 図 5 のように，与えられた直並列グラフ G の二分分解木. (c) 上の (b) で端子 s と t の役割を交換した場合である．. TBD の根を r とすると，G = Gr である．G∗r に対して 6. 詳しくは図 9(c) のように，G1 の外に端子 t から y + b. つの関数が計算されているとき，G に全域配送木があるか. だけ出力し，G1 の中に端子 s から a だけ入力する．. どうかは次のように判断できる．. また，G2 には端子 t から b だけ入力し，端子 s から. G(= Gr ) の端子 s と t がどちらもシンクのときには，. x + a だけフローが出力する．. fs,t (G∗ , dem(s), dem(t)) = 1 ならばグラフ G には全域. し た が っ て ，次 (a),(b) あ る い は (c) が 成 り 立 つ よ う. 配送木が存在し，fs,t (G∗ , dem(s), dem(t)) = 0 ならばグ. な a, b ∈ ZD が 存 在 す る と き ，か つ そ の と き に 限 り. ラフ G には全域配送木は存在しないと判断できる．ま. fs,t (G∗u , x, y) = 1 と計算できる．. た ，s と t の 片 方 ，例 え ば s が ソ ー ス w の と き に は ，. gts (G∗ , sup(w), dem(t)) = 1 ならばグラフ G には全域配. (a) fs,t (G∗1 , x + a, y + b) = 1 and g s,t (G∗2 , a, b) = 1. 送木が存在し，gts (G∗ , sup(w), dem(t)) = 0 ならばグラフ. (b). G には全域配送木は存在しないと判断できる． グラフ G の二分分解木 TBD の点 u. (c). に対して 6 つの関数を計算する方法を示す．図 2(a) のよう まれないので，fs,t , fst , fts は G∗u に対して定義されない．. x, y ∈ ZD に対して gts , gst , g s,t は次のように計算できる．. fts (G∗1 , a, y. (5). + b) = 1 and. gst (G∗2 , x + a, b) = 1. に Gu は 1 本の辺 e = (s, t) からなる．G∗u にはソースが含. (4). + a, b) = 1 and. gts (G∗2 , a, y + b) = 1. （b）二分分解木の葉 u での関数の計算方法 が葉であるとき，G∗u. fst (G∗1 , x. (6). （ii）次に fst (G∗u , x, y) の計算方法を示す．w は G1 に含ま れるとしよう．図 10 のように，fst (G∗u , x, y) を定義すると きのグラフ G∗u ′ の全域配送二木においては，ある a, b ∈ ZD. { gts (G∗u , x, y) =. 1. if y ≤ x and y ≤ cap(e);. 0. otherwise;. に対し，G1 の外に端子 s から x + a のフローが出力し，G1. (1). の中に端子 t から y − b だけ入力する．また，G2 の中に 端子 s と t から各々 a と b だけフローが入力される．した. { gst (G∗u , x, y) =. 1. if x ≤ y and x ≤ cap(e);. 0. otherwise;. がって，ある a, b ∈ ZD に対し次式が成り立つとき，かつ. (2). そのときに限り fst (G∗u , x, y) = 1 と計算できる．. fst (G∗1 , x + a, y − b) = 1 and g s,t (G∗2 , a, b) = 1 g s,t (G∗u , x, y) = 1.. (3). （c）TBD の内点 u が並列接続に対応しているときの関数の 計算方法. (7). （iii）fts (G∗u , x, y) は fst (G∗u , x, y) と同様にして計算で きる． （iv）次に gts (G∗u , x, y) の計算方法を示す．G∗u に w が含. 次にグラフ G の二分分解木 TBD の内点 u が並列接続に. まれていないとしてよい．gts (G∗u , x, y) を定義するときの. 対応しているときに６つの関数を計算する方法を示す．u. グラフ G∗u ′ の全域配送木 T は，ある a, b ∈ ZD に対し次の. の子を u1 , u2 とし，u1 に対応する直並列グラフを G1 と. ２つの場合がある．. し，u2 に対応する直並列グラフを G2 とする．このとき図. 2(d) のように G は G1 と G2 を並列接続して得られる． ⓒ 2013 Information Processing Society of Japan. (a) 図 11(a) のように，G1 の中に端子 s から x − a だけの フローが入力され，G1 の外に端子 t から y + b だけの. 5.
(6) Vol.2013-AL-143 No.10 2013/3/1. 情報処理学会研究報告 IPSJ SIG Technical Report. (a)Case(a). (a)Case(a). (b)Case(b). (b)Case(b) 図 11. gts (G∗u , x, y) のグラフ G∗u ′ の全域配送木. (c)Case(c) 図 9 fs,t (G∗u , x, y) のグラフ G∗u ′ の全域配送木 図 12. 図 10. 図 13. fst (G∗u , x, y) のグラフ G∗u ′ の全域配送二木. フローが出力される．一方，G2 には端子 s から a だ けのフローが入力され，端子 t から b だけのフローが. g s,t (G∗u , x, y) のグラフ G∗u ′ の全域配送二木. fs,t (G∗u , x, y) のグラフ G∗u ′ の全域配送木. （d）TBD の内点 u が直列接続に対応しているときの関数の 計算方法 二分分解木 TBD の内点 u が直列接続に対応していると. 入力される．. (b) 図 11(b) のように，G2 の中に端子 s から x − a だけの. きの計算方法を示す．u の子を u1 , u2 とし，u1 に対応す. フローが入力され，G2 の外に端子 t から y + b だけの. る直並列グラフを G1 とし，u2 に対応する直並列グラフを. フローが出力される．一方，G1 には端子 s から a だ. G2 とすると，図 2(c) のように G は G1 と G2 を直列接続. けのフローが入力され，端子 t から b だけのフローが. して得られる．G1 の端子 t1 と G2 の端子 s2 を同一視して 得られた点を v とすると，v は G においてシンクあるいは. 入力される． したがって，ある a, b ∈ ZD に対し次の (a) あるいは (b) が. ソースである．まず，G において接続点 v はシンクである. 成り立つとき，かつそのときに限り fs,t (G∗u , x, y) = 1 と計. 場合を考る．G∗u においては，v は端子でないので，むろん. 算できる．. v はシンクであり，その需要量は dem(v) であり，必ずし も 0 ではない．. (a) gts (G∗1 , x − a, y + b) = 1 and g. s,t. (G∗2 , a, b). =1. (b) g. s,t. (G∗1 , a, b). = 1 and. gts (G∗2 , x. − a, y + b) = 1. （i）まず fs,t (G∗u , x, y) の計算方法を示す．G∗u にソース. (8). てよい．（w が G2 に含まれる場合も同様である．）しかも. (9). （v）gst (G∗u , x, y) は gts (G∗u , x, y) と同様にして計算できる． （vi）次に g s,t (G∗u , x, y) の計算方法を示す．g s,t (G∗u , x, y) を定義するときのグラフ G∗u ′ の全域配送二木を図 12 に示 す．ある a, b ∈ ZD に対し次式が成り立つとき，かつその ときに限り g s,t (G∗u , x, y) = 1 と計算できることは明らかで ある．. g s,t (G∗1 , a, b) = 1 and g s,t (G∗2 , x − a, y − b) = 1 ⓒ 2013 Information Processing Society of Japan. w が含まれているとしてよい．w は G1 に含まれるとし w ̸= s, v である．fs,t (G∗u , x, y) を定義するときのグラフ G∗u ′ とその全域配送木 T を図 13 に示す．ある a ∈ ZD に対し次 式が成り立つとき，かつそのときに限り fs,t (G∗u , x, y) = 1 と計算すればよい．. fs,t (G∗1 , x, dem(v) + a) = 1 and gts (G∗2 , a, y) = 1 (11) （ii）次に fst (G∗u , x, y) の計算方法を示す．w は G1 に含 まれるとしよう．fst (Gu∗ , x, y) を定義するときのグラフ G∗u ′. (10). の全域配送二木は，ある a ∈ ZD に対し図 14（a）および. 6.
(7) Vol.2013-AL-143 No.10 2013/3/1. 情報処理学会研究報告 IPSJ SIG Technical Report. 図 14. 図 15. (a)Case(a). (a)Case(a). (b)Case(b). (b)Case(b). fst (G∗u , x, y) のグラフ G∗u ′ の全域配送二木. 図 16. gts (G∗u , x, y) のグラフ G∗u ′ の全域配送木. g s,t (G∗u , x, y) のグラフ G∗u ′ の全域配送二木. 図 17. fs,t (G∗u , x, y) のグラフ G∗u ′ の全域配送木. 図 18. fst (G∗u , x, y) のグラフ G∗u ′ の全域配送二木. （b）に示す２つの場合がある．したがって，ある a ∈ ZD に対し次の（a）あるいは（b）が成り立つとき，かつその ときに限り fst (G∗u , x, y) = 1 と計算できる．. (a). fs,t (G∗1 , x, dem(v) g. (b). s,t. (G∗2 , a, y). fst (G∗1 , x, a) gst (G∗2 , a. + a) = 1 and. =1. (12). = 1 and. + dem(v), y) = 1. （i）まず fs,t (G∗u , x, y) の計算方法を示す．fs,t (G∗u , x, y) を定義するときのグラフ G∗u ′ の全域配送木を図 17 に示す． ある a ∈ ZD に対し次式が成り立つとき，かつそのときに. (13). 限り fs,t (G∗u , x, y) = 1 と計算すればよい．. （iii）fts (G∗u , x, y) は fst (G∗u , x, y) と同様にして計算で きる． （iv）次に gts (G∗u , x, y) の計算方法を示す．G∗u に w が 含まれていないとしてよい．gts (G∗u , x, y) を定義すると きのグラフ G∗u ′ とその全域配送木を図 15 に示す．ある. a ∈ ZD に対し次式が成り立つとき，かつそのときに限り gts (G∗u , x, y) = 1 と計算すればよい． gts (G∗1 , x, dem(v) + a) = 1 and gts (G∗2 , a, y) = 1. (14). （v） gst (G∗u , x, y) は gts (G∗u , x, y) と同様にして計算で きる． （vi）次に g s,t (G∗u , x, y) の計算方法を示す．G∗u にソー ス w が含まれていないとしてよい．g s,t (G∗u , x, y) を定義 するときのグラフ G∗u ′ の全域配送二木は，ある a ∈ ZD に 対し図 16（a）および（b）に示す２つの場合がある．した がて，ある a ∈ ZD に対し次の（a）あるいは（b）が成り 立つとき，かつそのときに限り g s,t (G∗u , x, y) = 1 と計算で きる．. (15). ⓒ 2013 Information Processing Society of Japan. を定義するときのグラフ G∗u ′ の全域配送二木を図 18 に示 す．ある a ∈ ZD に対し次式が成り立つとき，かつそのと きに限り fst (G∗u , x, y) = 1 と計算すればよい．. gst (G∗1 , x, a) = 1 and g s,t (G∗2 , sup(w) − a, y) = 1 (18) （iii）fts (G∗u , x, y) は fst (G∗u , x, y) と同様にして計算する ことができる．. 3.4 計算時間 直並列グラフ G の二分分解木 TBD の任意の葉 u に対して， 関数 gts , gst , g s,t は式 (1)–(3) を用いて O(|ZD |2 ) = O(D2 ) 時間で計算することができる．ここで D は需要量の合計 である．G は n 点からなり，G は単純直並列グラフである としてよいので，G の辺は高々 2n − 3 本しかなく，TBD に. きる．. TBD の任意の内部点 u に対して，６つの関数は式 (4)–(18) (16). 最後に G1 と G2 の接続点 v がソース w であるときの計 算方法を示す．. （ii）次に fst (G∗u , x, y) の計算方法を示す．fst (G∗u , x, y). の葉に対して 6 つの関数を計算するのは O(D2 n) 時間でで. (b) g s,t (G∗1 , x, a) = 1 and gst (G∗2 , dem(v) + a, y) = 1. (17). は葉が高々 2n − 3 枚しかない．したがって，TBD の全て. (a) gts (G∗1 , x, dem(v) + a) = 1 and g s,t (G∗2 , a, y) = 1. gst (G∗1 , x, a) = 1 and gts (G∗2 , sup(w) − a, y) = 1. を用いて O(|ZD |4 ) = O(D4 ) 時間で計算することができる． 二分木 TBD には高々 2n − 4 個の内点しかないので，TBD の全ての内点に対し６つの関数を計算するのは O(D4 n) 時 間でできる．このようにして次の定理が得られる．. 7.
(8) Vol.2013-AL-143 No.10 2013/3/1. 情報処理学会研究報告 IPSJ SIG Technical Report. 定理 2. n 点からなる直並列グラフに対し全域配送木問. 題は O(D4 n) で解ける．. [5]. 4. 結論 本文では，まず全域配送木問題を定式化し，直並列グラ. [6]. フに対してすら NP 完全であることを示した．次に点数を. n，需要量の合計を D としたときに，直並列グラフの全域 配送木問題を O(D4 n) 時間で解く擬多項式時間アルゴリズ. [7]. ムを与えた．D が n の多項式以下ならば，そのアルゴリズ. [8]. ムの計算時間は n の多項式であり，D が定数ならば線形時 間である．なお，本文のアルゴリズムを修正すれば，全域 配送木を具体的に見つけることもできる． 本文のアルゴリズムを拡張すれば，ソースが 1 個とは限. [9]. らず複数個ある直並列グラフに対する全域配送林問題も擬 多項式時間で解くことができる．また，与えられたグラフ. G が部分 k 木，即ち木幅が定数 k 以下であるときにも [6]，. [10]. 全域配送木問題や全域配送林問題を擬多項式時間で解くこ とができる．. [11]. 与えられたグラフ G に全域配送木がないときには，ソー ス w を含む配送木 T で，T に含まれるシンクの需要量の合 計が最大なもの，即ち 最大配送木 を求めたい．無論この. [12]. 最大配送木問題 は直並列グラフに対してすら NP-困難であ る．ソースが複数ある場合には，同様にして 最大配送林 が. [13]. 定義される．G が木である場合には，辺容量がないとき [7] および辺容量があるとき [8] に対し，最大配送林を近似的 に求める FPTAS が与えられている．また，辺容量がない 直並列グラフや部分 k 木に対しては，最大配送林が擬多項. [14]. (Twenty-second printing),” W.H. FREEMAN AND COMPANY (2000), pp. 90-91. T. Ito, E. D. Demaine, X. Zhou and T. Nishizeki, “Approximability of partitioning graphs with supply and demand,” Journal of Discrete Algorithms, 6 (2008), pp. 627-650. T. Ito, X. Zhou and T. Nishizeki, “Partitioning graphs of supply and demand,” Discrete Applied Math., 157(2009), pp. 2620-2633. T. Ito, X. Zhou and T. Nishizeki, “Partitioning trees of supply and demand,” IJFCS 16, 4(2005), pp. 803-827. M. Kawabata and T. Nishizeki, “Prtitioning trees with supply, demand and edge-capacity,” Proc. of ISORA 2011, Lecture Notes in Operation Research, Vol. 14 (2011), pp. 51-58, also IEICE Trans. on Fundamentals of Electronics, Communications and Computer Science, to appear. M. S. Kim, S. S. Lam and D.-Y. Lee, “Optimal distribution tree for internet streaming media,” Proc. 23rd Int. Conf. on Distributed Computing System(ICDCS ’03), (2003), pp. 116-125. J. M. Kleinberg, “Single-source unsplittable flow,” Proc. of 37th FOCS (1996), pp.68-77. A. B. Morton and I. M. Y. Mareels, “An efficient bruteforce solution to the network reconfiguration problem,” IEEE Trans. on Power Delivery 15, 3(2000), pp. 9961000. T. Nishizeki, J. Vygen and X. Zhou, “The edge-disjoint paths problem is NP-complete for series-parallel graphs,” Discrete Applied Math., 115(2001), pp. 177-186. K. Takamizawa, T. Nishizeki and N. Saito, “Lineartime computability of combinatorial problems on seriesparallel graphs,” J. Assoc. Comput. Mach. 29 (1982), pp.6 23-641. J-H. Teng and C-N. Lu, “Feeder-switch relocation for customer interruption cost minimization,” IEEE Trans. on Power Delivery 17, 1(2002), pp. 254-259.. 式時間で求まる [6]．今後は辺容量がある直並列グラフや 部分 k 木に対して最大配送木問題や最大配送林問題を近似 的に解く FPTAS を求めることが望まれる．なお，辺容量 がない直並列グラフの最大配送木問題に対しては FPTAS が与えられている [5]． 謝辞 全域配送木問題の NP 完全性の証明に関し有益な コメントを頂いた今川廣二氏に感謝します．本研究の一部 は文部科学省私立大学戦略的基盤形成支援事業により実施 された． 参考文献 [1]. [2]. [3]. [4]. N. G. Boulaxis and M. P. Papadopoulos, “Optimal feeder routing in distribution system planning using dynamic programming technique and GIS facilities,” IEEE Trans. on Power Delivery 17, 1(2002), pp. 242-247. C. Chekuri, A. Ene and N. Korula, “Unsplittable flow in paths and trees and column-restricted packing integer programs,” Proc. APPROX-RANDOM 2009(2009), pp. 42-55. Y. Dinitz, N. Garg and M. X. Goemans, “On the singlesource unsplittable flow problem,” Combinatorica 19, 1 (1999), pp. 17-41. M. R. Garey and D. S. Johnson, “Computers and Intractability, A Guide to the Theory of NP-Completeness. ⓒ 2013 Information Processing Society of Japan. 8.
(9)
関連したドキュメント
Considering the optimal tactical decisions regarding service level, transfer price, and marketing expenditure, manufacturer of the new SC has to decide how to configure his
A NOTE ON SUMS OF POWERS WHICH HAVE A FIXED NUMBER OF PRIME FACTORS.. RAFAEL JAKIMCZUK D EPARTMENT OF
For the case of rectangles, we show that, for any given edge-weighted planar graph whose outer face is a quadrangle, that is internally triangulated and that has no
For example, random geometric graphs are formed by randomly assign- ing points in a Euclidean space to vertices and then adding edges deterministically between vertices when
A lemma of considerable generality is proved from which one can obtain inequali- ties of Popoviciu’s type involving norms in a Banach space and Gram determinants.. Key words
de la CAL, Using stochastic processes for studying Bernstein-type operators, Proceedings of the Second International Conference in Functional Analysis and Approximation The-
[3] JI-CHANG KUANG, Applied Inequalities, 2nd edition, Hunan Education Press, Changsha, China, 1993J. FINK, Classical and New Inequalities in Analysis, Kluwer Academic
Chapoton pointed out that the operads governing the varieties of Leibniz algebras and of di-algebras in the sense of [22] may be presented as Manin white products of the operad
