TR#: | CS0617 |

Class: | CS |

Title: | ON SEYMOUR'S AND LOMONOSOV'S PLANE INTEGRAL TWO COMMODITY FLOW RESULTS |

Authors: | E. Korach and M. Penn |

CS0617.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. |

Copyright | The 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