Show simple item record

dc.contributor.authorTuza, Zsolt
dc.contributor.authorBazgan, Cristina
dc.date.accessioned2010-03-09T14:42:25Z
dc.date.available2010-03-09T14:42:25Z
dc.date.issued2008
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3675
dc.language.isoenen
dc.subjectMaximum cuten
dc.subjectCubic graphen
dc.subjectApproximation algorithmen
dc.subjectVertex decompositionen
dc.subjectUnicyclic graphen
dc.subject.ddc511en
dc.titleCombinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3en
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe best approximation algorithm for Max Cut in graphs of maximum degree 3 uses semidefinite programming, has approximation ratio 0.9326, and its running time is Θ(n3.5logn); but the best combinatorial algorithms have approximation ratio 4/5 only, achieved in O(n2) time [J.A. Bondy, S.C. Locke, J. Graph Theory 10 (1986) 477–504; E. Halperin, et al., J. Algorithms 53 (2004) 169–185]. Here we present an improved combinatorial approximation, which is a 5/6-approximation algorithm that runs in O(n2) time, perhaps improvable even to O(n). Our main tool is a new type of vertex decomposition for graphs of maximum degree 3.en
dc.relation.isversionofjnlnameJournal of Discrete Algorithms
dc.relation.isversionofjnlvol6en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2008-09
dc.relation.isversionofjnlpages510-519en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.jda.2007.02.002en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelPrincipes généraux des mathématiquesen


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