EPrints@IIT Delhi >
Faculty Research Publicatons  >
Computer Science and Engineering >

Please use this identifier to cite or link to this item: http://eprint.iitd.ac.in/handle/2074/2405

Full metadata record

DC FieldValueLanguage
dc.contributor.authorTardos, Éva-
dc.contributor.authorVazirani, Vijay V-
dc.identifier.citationInformation Processing Letters, 47(2), 77-80p.en
dc.description.abstractWe consider the version of the multicommodity flow problem in which the objective is to maximize the sum of commodities routed. Garg, Vazirani and Yannakakis proved that the minimum multicut and maximum flow ratio for this problem can be bounded by O(log k), where k is the number of commodities. In this note we improve this ratio to O(1) for planar graphs, and more generally to O(r3) for graphs with an excluded Kr, r minor. The proof is based on the network decomposition theorem of Klein, Plotkin and Rao. Our proof is constructive and yields approximation algorithms, with the same factors, for the minimum multicut problem on such networks.en
dc.format.extent147118 bytes-
dc.subjectanalysis of algorithmsen
dc.subjectcomputational complexityen
dc.subjectgraph theoryen
dc.titleImproved bounds for the max-flow min-multicut ratio for planar and Kr, r-free graphsen
Appears in Collections:Computer Science and Engineering

Files in This Item:

File Description SizeFormat
tardosimp93.pdf143.67 kBAdobe PDFView/Open
View Statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback