DSpace
 

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/1332

Full metadata record

DC FieldValueLanguage
dc.contributor.authorGarg, Naveen-
dc.contributor.authorVazirani, Vijay V-
dc.contributor.authorYannakakis, Mihalis-
dc.date.accessioned2006-02-20T06:55:31Z-
dc.date.available2006-02-20T06:55:31Z-
dc.date.issued2004-
dc.identifier.citationJournal of Algorithms, 50(1), 49-61en
dc.identifier.urihttp://eprint.iitd.ac.in/dspace/handle/2074/1332-
dc.description.abstractA (2−2/k) approximation algorithm is presented for the node multiway cut problem, thus matching the result of Dahlhaus et al. (SIAM J. Comput. 23 (4) (1994) 864–894) for the edge version of this problem. This is done by showing that the associated LP-relaxation always has a half-integral optimal solution.en
dc.format.extent150371 bytes-
dc.format.mimetypeapplication/pdf-
dc.language.isoenen
dc.subjectapproximation algorithmen
dc.subjectLP-relaxationen
dc.titleMultiway cuts in node weighted graphsen
dc.typeArticleen
Appears in Collections:Computer Science and Engineering

Files in This Item:

File Description SizeFormat
gargmul2004.pdf146.85 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