2014/10/27 by Maxim A. Babenko, Babenko, Maxim A., Alexander V. Karzanov +1
Computer Science · Engineering · #05C10 #05C21 #05C85 #90C27 #Advanced Manufacturing and Logistics Optimization #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Search Problems #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.1410.7208
openalex publication_date 2014/10/27 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
We consider an undirected multi(commodity)flow demand problem in which a\nsupply graph is planar, each source-sink pair is located on one of three\nspecified faces of the graph, and the capacities and demands are integer-valued\nand Eulerian. It is known that such a problem has a solution if the cut and\n(2,3)-metric conditions hold, and that the solvability implies the existence of\nan integer solution. We develop a purely combinatorial strongly polynomial\nsolution algorithm.\n