09 2017/10 11
01 020304050607
1516 1718192021
22 232425262728
Click セミナー


発表者松岡 達也 
発表者の紹介東京大学 博士後期課程
タイトル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