Playing with Parameters: Cross-parameterization in GraphsReportar como inadecuado




Playing with Parameters: Cross-parameterization in Graphs - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

* Corresponding author 1 SAMM - Statistique, Analyse et Modélisation Multidisciplinaire SAmos-Marin Mersenne 2 ESSEC Business School 3 ESSEC Business School 4 LAMSADE - Laboratoire d-analyse et modélisation de systèmes pour l-aide à la décision

Abstract : When considering a graph problem from a parameterized point of view, the parameter chosen is often the size of an optimal solution of this problem the -standard-. A natural subject for investigation is what happens when we parameterize such a problem by the size of an optimal solution of a different problem. We provide a framework for doing such analysis. In particular, we investigate seven natural vertex problems, along with their respective parameters: α the size of a maximum independent set, τ the size of a minimum vertex cover, ω the size of a maximum clique, χ the chromatic number, γ the size of a minimum dominating set, i the size of a minimum independent dominating set and ν the size of a minimum feedback vertex set. We study the parameterized complexity of each of these problems with respect to the standard parameter of the others.





Autor: Nicolas Bourgeois - Konrad Kazimierz Dabrowski - Marc Demange - Vangelis Paschos -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados