
Using greediness for parameterization: the case of max and min (k, n − k)-cut
Bonnet, Édouard; Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012), Using greediness for parameterization: the case of max and min (k, n − k)-cut. https://basepub.dauphine.fr/handle/123456789/12148
View/ Open
Type
Document de travail / Working paperDate
2012Publisher
Université Paris-Dauphine
Series title
Cahiers du LamsadePublished in
Paris
Pages
13
Metadata
Show full item recordAuthor(s)
Bonnet, Édouard
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Escoffier, Bruno
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Tourniaire, Emeric
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
MAX (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.Subjects / Keywords
Algorithme et structure de données; ComplexitéRelated items
Showing items related by title and author.
-
Bonnet, Édouard; Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2015) Article accepté pour publication ou publié
-
Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2014) Article accepté pour publication ou publié
-
Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012) Communication / Conférence
-
Escoffier, Bruno; Paschos, Vangelis (2005) Communication / Conférence
-
Paschos, Vangelis; Escoffier, Bruno (2007) Article accepté pour publication ou publié