On Extremal Multiflows

✍ Scribed by Hagai Ilani; Ephraim Korach; Michael Lomonosov

• Book ID: 102583452
• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 265 KB
• Volume: 79
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.2000.1958

✦ Synopsis

Given an Eulerian multigraph, a subset T of its vertices, and a collection H of subsets of T, we ask how few edge-disjoint paths can contain maximum (A, T "A)flows, for all A # H at once. We answer the question for a certain class of hypergraphs H by presenting a strongly polynomial construction of a minimum set of such paths and a min-max formula for its cardinality. The method consists in reducing the problem to maximizing a b-matching in some graph. The result provides a solution to one interesting class of path packing problems. 2000