skip to main content

Idioma:

On the Parameterized Complexity of Graph Modification to First-Order Logic Properties

Fomin, Fedor V. ; Golovach, Petr A. ; Thilikos, Dimitrios M.

Theory of computing systems, 2020-02, Vol.64 (2), p.251-271 [Revista revisada por pares]

New York: Springer US

Texto completo disponible

Citas Citado por

Acciones

Título:
On the Parameterized Complexity of Graph Modification to First-Order Logic Properties
Autor: Fomin, Fedor V. ; Golovach, Petr A. ; Thilikos, Dimitrios M.
Materias: Apexes ; Combinatorics ; Complexity ; Computational Complexity ; Computer Science ; Data Structures and Algorithms ; Graph theory ; Logic ; Logic in Computer Science ; Mathematics ; Parameter modification ; Parameterization ; Polynomials ; Theory of Computation
Es parte de: Theory of computing systems, 2020-02, Vol.64 (2), p.251-271
Descripción: We establish connections between parameterized/kernelization complexity of graph modification problems and expressibility in logic. For a first-order logic formula φ , we consider the problem of deciding whether an input graph can be modified by removing/adding at most k vertices/edges such that the resulting modification has the property expressible by φ . We provide sufficient and necessary conditions on the structure of the prefix of φ specifying when the corresponding graph modification problem is fixed-parameter tractable (parameterized by k ) and when it admits a polynomial kernel.
Editor: New York: Springer US
Idioma: Inglés

Enlaces

View record in HAL

Volver a la lista de resultados

Ir a la página anterior

Anterior Resultado 8 Siguiente Ir a la siguiente página

Ir a la siguiente página

Realización: Logos de Redes Sociales:

Buscando en bases de datos remotas, por favor espere

Buscando por
enscope:(USP_VIDEOS),scope:("PRIMO"),scope:(USP_FISICO),scope:(USP_EREVISTAS),scope:(USP),scope:(USP_EBOOKS),scope:(USP_PRODUCAO),primo_central_multiple_fe
Mostrar lo que tiene hasta ahora