arXiv Analytics

Sign in

arXiv:1410.7208 [math.CO]AbstractReferencesReviewsResources

A combinatorial algorithm for the planar multiflow problem with demands located on three holes

Maxim A. Babenko, Alexander V. Karzanov

Published 2014-10-27Version 1

We consider an undirected multi(commodity)flow demand problem in which a supply graph is planar, each source-sink pair is located on one of three specified faces of the graph, and the capacities and demands are integer-valued and Eulerian. It is known that such a problem has a solution if the cut and (2,3)-metric conditions hold, and that the solvability implies the existence of an integer solution. We develop a purely combinatorial strongly polynomial solution algorithm.

Comments: 16 pages, 4 figures
Categories: math.CO
Subjects: 90C27, 05C10, 05C21, 05C85
Related articles: Most relevant | Search more
arXiv:2004.10443 [math.CO] (Published 2020-04-22)
A combinatorial algorithm for computing the rank of a generic partitioned matrix with $2 \times 2$ submatrices
arXiv:2104.14841 [math.CO] (Published 2021-04-30)
A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with $2 \times 2$ submatrices
arXiv:math/0601483 [math.CO] (Published 2006-01-19)
A Little bijection for affine Stanley symmetric functions

Links

Toolbox