10 2017/11 12
29303101020304
05060708091011
12131415161718
19 202122232425
26 272829300102
Click セミナー

過去のセミナー

開催日2017年10月24日(火曜日)
開催時間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
接続サイト神田オフィス