グラフの全域配送林を見つけるアルゴリズム

井上 惠介  西関 隆夫  

誌名
電子情報通信学会論文誌 D   Vol.J98-D   No.3   pp.353-362
発行日: 2015/03/01
Online ISSN: 1881-0225
論文種別: 特集論文 (学生論文特集)
専門分野: 情報・システム基礎
キーワード: 
全域配送林,  直並列グラフ,  木幅限定グラフ,  ネットワーク,  フロー,  

本文: PDF(969.7KB)
>>論文を購入


あらまし: 
グラフGにはソースがl個あるとし,各ソースには供給量と呼ばれる非負整数が割り当てられ,ソース以外の点は全てシンクであり,需要量と呼ばれる非負整数が割り当てられ,各辺には容量と呼ばれる非負整数が割り当てられているとする.Gの全域林Fが全域配送林と呼ばれるのは,林Fl本の木からなり,各木Tにはソースが丁度1個含まれており,そのソースからTに含まれる各シンクへ需要量だけのフローをT上の道に沿って流したときに,各辺に流れるフローの値がその辺容量以下であるときである.全域配送林問題とは,与えられたグラフGに全域配送林Fが存在するかどうか判定する問題である.本文では,直並列グラフに対し全域配送林問題を解く擬多項式時間アルゴリズムを与える.そのアルゴリズムは木幅限定グラフに拡張できるので,その概要も与える.