• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Book chapter

A Combinatorial Algorithm for the Planar Multiflow Problem with Demands Located on Three Holes

P. 53-66.
Babenko M. A., Karzanov A.

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.

In book

Edited by: L. Berlemishev, D. Musatov. Vol. 9139. Springer, 2015.