Show simple item record

dc.contributor.authorBonnet, Édouard*
dc.contributor.authorEscoffier, Bruno*
dc.contributor.authorPaschos, Vangelis*
dc.contributor.authorTourniaire, Emeric*
dc.date.accessioned2013-11-22T13:29:38Z
dc.date.available2013-11-22T13:29:38Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/12148
dc.language.isoenen
dc.subjectAlgorithme et structure de données
dc.subjectComplexité
dc.subject.ddc003en
dc.titleUsing greediness for parameterization: the case of max and min (k, n − k)-cut
dc.typeDocument de travail / Working paper
dc.description.abstractenMAX (k, n−k)-CUT (resp., MIN (k, n−k)-CUT) is a constrained version of MAX-CUT (resp.,MIN-CUT) where one has to find a bipartition of the vertex set into two subsets with respectively k and n − k vertices (n being the total number of vertices of the input graph) which maximizes (resp., minimizes) the number of edges going from one subset to the other. In this paper, we investigate the parameterized complexity of these two graph problems by considering several parameters, such as the value p of the solution, k, the size á of a minimum vertex cover and the treewidth tw of the input graph. We also give approximation schemata in FPT time for parameterizations which turn out to be W[1]-hard.
dc.publisher.nameUniversité Paris-Dauphine
dc.publisher.cityParisen
dc.identifier.citationpages13
dc.relation.ispartofseriestitleCahiers du Lamsade
dc.identifier.urlsitehttps://hal.archives-ouvertes.fr/hal-00874363
dc.subject.ddclabelRecherche opérationnelleen
dc.description.submittednonen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2017-02-09T16:19:13Z
hal.person.labIds989*
hal.person.labIds989*
hal.person.labIds989*
hal.person.labIds989*


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