Show simple item record

dc.contributor.authorKaminski, Marcin
dc.contributor.authorDella Croce, Federico
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2009-10-12T13:14:10Z
dc.date.available2009-10-12T13:14:10Z
dc.date.issued2007
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2207
dc.language.isoenen
dc.subjectSparse graphsen
dc.subjectExact algorithmen
dc.subjectMAX-CUTen
dc.subject.ddc003en
dc.titleAn exact algorithm for MAX CUT in sparse graphsen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherD.A.I., Politecnico di Torino;Italie
dc.contributor.editoruniversityotherRUTCOR, Rutgers University;États-Unis
dc.description.abstractenWe study exact algorithms for the MAX-CUT problem. Introducing a new technique, we present an algorithmic scheme that computes a maximum cut in graphs with bounded maximum degree. Our algorithm runs in time O*(2(1-(2/Δ))n). We also describe a MAX-CUT algorithm for general graphs. Its time complexity is O*(2mn/(m+n)). Both algorithms use polynomial space.en
dc.relation.isversionofjnlnameOperations Research Letters
dc.relation.isversionofjnlvol35en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2007
dc.relation.isversionofjnlpages403-408en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.orl.2006.04.001en
dc.identifier.urlsitehttp://hal.archives-ouvertes.fr/hal-00116633/en/
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record