Technical Report CS0617

TR#:CS0617
Class:CS
Title: ON SEYMOUR'S AND LOMONOSOV'S PLANE INTEGRAL TWO COMMODITY FLOW RESULTS
Authors: E. Korach and M. Penn
PDFCS0617.pdf
Abstract: We consider the maximum integral tWo-Commodity flow problem in augmented planar graphs (i.e., with both source-sink edges added) and provide an o(IVI21ogIVI) algorithm for that problem. Let G =(V, E) be a graph and w : E -t Z+ a weight function. Let T C V be an even subset of the vertices of G. A T-cut is an edge-cutset of the graph which divides T into two odd sets. Lomonosov gave a good characterization of augmented, planar graphs for which the maximum two-commodity flow is integral. We derive Lomonosov's characterization by using results of Seymour on integral packing of T-cuts in the case ITI = 4, and on the correspondence between plane integral multicommodity flow and integral packing of T-cuts.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1990/CS/CS0617), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1990
To the main CS technical reports page

Computer science department, Technion
admin