12 2017/01 02
01020304050607
08091011121314
15161718192021
2223 2425262728
29 303101020304
Click セミナー

次回セミナー

開催日2017年10月23日(月曜日)
開催時間13時00分-14時00分
発表者松岡 達也 
発表者の紹介東京大学 博士後期課程
タイトルPolymatroid-Based Capacitated Packing of Branchings 
発表の概要
Edmonds (1973) characterized the condition for the existence of a packing of spanning arborescences and also that of spanning branchings in a directed graph and gave polynomial-time algorithms to find such packings if they exist. Durand de Gevigney, Nguyen and Szigeti (2013) generalized the first problem and solved the matroid-based arborescence packing problem. We consider the polymatroid-based arborescence packing problem, which is a generalization of the latter problem. We formulate two problem settings: the unsplittable version and the splittable version. We show that the unsplittable version is strongly NP-complete. Whereas, for the splittable version, which generalizes the capacitated version of the spanning arborescence packing problem, we show that this problem can be solved in strongly polynomial time. Actually, we provide a strongly polynomial-time algorithm for the problem of the polymatroid-based capacitated packing of branchings for this version. This is a joint work with Zoltán Szigeti.
開催場所VBL 301B
接続サイト神田オフィス