@PhdThesis{Gonzales2024,
   author       = {Carolina Lucía Gonzales},
   title        = {Problemas localmente verificables parametrizados por treewidth, clique-width y mim-width},
   school       = {Facultad de Ciencias Exactas y Naturales/UBA},
   year         = {2024},
   month        = {abril},
   day          = {15},
   type         = {Doutorado},
   note         = {Orientador: Flavia Bonomo.  Banca: Sergio Cabello Justo,
                  Paloma T. de Lima e Dimiotriou Touloupas.},
   keywords     = {OrDScC,Universal2021},
   abstract     = {Intuitively, a locally checkable problem is a vertex partition problem (or, equivalently, a vertex coloring problem) for which a solution can be verified simply by checking
a certain local property for each vertex, that is, a property that involves only the solution restricted to the vertex and its neighbors. This is the case of several variants of
domination, independent set and k-coloring, among other problems. There exist numerous frameworks that include a large subset of these problems, for which algorithms
have been proposed to solve them efficiently in various graph classes.
In this thesis we define a new framework for locally checkable problems, formalizing the intuitive notion we have of them to then analyze under what circumstances
we can propose efficient algorithms to solve them. The proposed algorithms are based
on dynamic programming and we computed their complexities when parameterized
by treewidth, clique-width and mim-width. The results obtained generalize those of
previously defined frameworks. We further show how to model within our framework
several problems in the literature, such as [k]-Roman domination, k-community and
Grundy domination, thus proving that they are FPT or XP when parameterized by
treewidth, clique-width or mim-width. Moreover, we propose polynomial-time approximation schemes for some locally checkable problems in planar graphs. },
   __url_pdf    = {}
}

{"_id":"5hguSr4J4MPP6mvx3","bibbaseid":"gonzales-problemaslocalmenteverificablesparametrizadosportreewidthcliquewidthymimwidth-2024","author_short":["Gonzales, C. L."],"bibdata":{"bibtype":"phdthesis","type":"Doutorado","author":[{"firstnames":["Carolina","Lucía"],"propositions":[],"lastnames":["Gonzales"],"suffixes":[]}],"title":"Problemas localmente verificables parametrizados por treewidth, clique-width y mim-width","school":"Facultad de Ciencias Exactas y Naturales/UBA","year":"2024","month":"abril","day":"15","note":"Orientador: Flavia Bonomo. Banca: Sergio Cabello Justo, Paloma T. de Lima e Dimiotriou Touloupas.","keywords":"OrDScC,Universal2021","abstract":"Intuitively, a locally checkable problem is a vertex partition problem (or, equivalently, a vertex coloring problem) for which a solution can be verified simply by checking a certain local property for each vertex, that is, a property that involves only the solution restricted to the vertex and its neighbors. This is the case of several variants of domination, independent set and k-coloring, among other problems. There exist numerous frameworks that include a large subset of these problems, for which algorithms have been proposed to solve them efficiently in various graph classes. In this thesis we define a new framework for locally checkable problems, formalizing the intuitive notion we have of them to then analyze under what circumstances we can propose efficient algorithms to solve them. The proposed algorithms are based on dynamic programming and we computed their complexities when parameterized by treewidth, clique-width and mim-width. The results obtained generalize those of previously defined frameworks. We further show how to model within our framework several problems in the literature, such as [k]-Roman domination, k-community and Grundy domination, thus proving that they are FPT or XP when parameterized by treewidth, clique-width or mim-width. Moreover, we propose polynomial-time approximation schemes for some locally checkable problems in planar graphs. ","__url_pdf":"","bibtex":"@PhdThesis{Gonzales2024,\n author = {Carolina Lucía Gonzales},\n title = {Problemas localmente verificables parametrizados por treewidth, clique-width y mim-width},\n school = {Facultad de Ciencias Exactas y Naturales/UBA},\n year = {2024},\n month = {abril},\n day = {15},\n type = {Doutorado},\n note = {Orientador: Flavia Bonomo. Banca: Sergio Cabello Justo,\n Paloma T. de Lima e Dimiotriou Touloupas.},\n keywords = {OrDScC,Universal2021},\n abstract = {Intuitively, a locally checkable problem is a vertex partition problem (or, equivalently, a vertex coloring problem) for which a solution can be verified simply by checking\na certain local property for each vertex, that is, a property that involves only the solution restricted to the vertex and its neighbors. This is the case of several variants of\ndomination, independent set and k-coloring, among other problems. There exist numerous frameworks that include a large subset of these problems, for which algorithms\nhave been proposed to solve them efficiently in various graph classes.\nIn this thesis we define a new framework for locally checkable problems, formalizing the intuitive notion we have of them to then analyze under what circumstances\nwe can propose efficient algorithms to solve them. The proposed algorithms are based\non dynamic programming and we computed their complexities when parameterized\nby treewidth, clique-width and mim-width. The results obtained generalize those of\npreviously defined frameworks. We further show how to model within our framework\nseveral problems in the literature, such as [k]-Roman domination, k-community and\nGrundy domination, thus proving that they are FPT or XP when parameterized by\ntreewidth, clique-width or mim-width. Moreover, we propose polynomial-time approximation schemes for some locally checkable problems in planar graphs. },\n __url_pdf = {}\n}\n\n","author_short":["Gonzales, C. L."],"key":"Gonzales2024","id":"Gonzales2024","bibbaseid":"gonzales-problemaslocalmenteverificablesparametrizadosportreewidthcliquewidthymimwidth-2024","role":"author","urls":{},"keyword":["OrDScC","Universal2021"],"metadata":{"authorlinks":{}}},"bibtype":"phdthesis","biburl":"http://www.inf.ufpr.br/teoria/universal2021/orientacoes.bib","dataSources":["A5KFFBhQF4wDQsTFG"],"keywords":["ordscc","universal2021"],"search_terms":["problemas","localmente","verificables","parametrizados","por","treewidth","clique","width","mim","width","gonzales"],"title":"Problemas localmente verificables parametrizados por treewidth, clique-width y mim-width","year":2024}