Leírás
EGERVÁRY seminar
Abstract: Since the fundamental result of Edmonds on arborescence packings, intensive research has been done for extending this result. Recently, Gao and Yang observed that considering the strong components is useful in this theory. By using this idea, Hörsch and Szigeti found the proof from the Book for the packing results where a reachability condition is considered, for example, they showed how to prove the result of Katoh, Kamiyama and Takizawa from Edmonds' (strong) theorem. In the first part of my talk I will present their approach.
We have showed with Szigeti, Tanigawa how the edge sets of the packings in the most recent results can be characterized via matroid intersections by extending another result of Edmonds and extended the characterization for a case where further matroid constraints are added. We show that the above mentioned idea of using strong components give rise to simplified proofs for these results.
We also provide a characterization of the edge sets of arborescence packings in mixed graphs via matroid intersection. This latter results gives rise to a polynomial algorithm to find the minimum cost of such packings.
The talk will be in English.
Please contact Tamás Király (tkiraly[at]cs.elte.hu) for Zoom access.