Algorithms parameterized by vertex cover and modular width, through potential maximal cliques

Fedor V. Fomin, Mathieu Liedloff, Pedro Montealegre, Ioan Todinca

Resultado de la investigación: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

12 Citas (Scopus)

Resumen

In this paper we give upper bounds on the number of minimal separators and potential maximal cliques of graphs w.r.t. two graph parameters, namely vertex cover (vc) and modular width (mw). We prove that for any graph, the number of minimal separators is O*(3vc and O*(1.6181mw), the number of potential maximal cliques is O*(4vc) and O*(1.7347mw), and these objects can be listed within the same running times. (The O* notation suppresses polynomial factors in the size of the input.) Combined with known results [3,12], we deduce that a large family of problems, e.g., Treewidth, Minimum Fill-in, Longest Induced Path, Feedback vertex set and many others, can be solved in time O*(4vc or O*(1.7347mw).

Idioma originalInglés
Título de la publicación alojadaAlgorithm Theory, SWAT 2014 - 14th Scandinavian Symposium and Workshops, Proceedings
EditorialSpringer Verlag
Páginas182-193
Número de páginas12
ISBN (versión impresa)9783319084039
DOI
EstadoPublicada - 2014
Evento14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014 - Copenhagen, Dinamarca
Duración: 2 jul. 20144 jul. 2014

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen8503 LNCS
ISSN (versión impresa)0302-9743
ISSN (versión digital)1611-3349

Conferencia

Conferencia14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014
País/TerritorioDinamarca
CiudadCopenhagen
Período2/07/144/07/14

Huella

Profundice en los temas de investigación de 'Algorithms parameterized by vertex cover and modular width, through potential maximal cliques'. En conjunto forman una huella única.

Citar esto