skip to main content

On the parameterized complexity of vertex cover and edge cover with connectivity constraints

Fernau, Henning ; Fomin, Fedor V ; Philip, Geevarghese ; Saurabh, Saket

Theoretical Computer Science, 02 February 2015, Vol.565, pp.1-15 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por
  • Título:
    On the parameterized complexity of vertex cover and edge cover with connectivity constraints
  • Autor: Fernau, Henning ; Fomin, Fedor V ; Philip, Geevarghese ; Saurabh, Saket
  • Assuntos: Parameterized Complexity ; Connectivity Problems ; Kernel Lower Bounds ; Vertex Cover ; Edge Cover ; Computer Science ; Mathematics
  • É parte de: Theoretical Computer Science, 02 February 2015, Vol.565, pp.1-15
  • Descrição: We investigate the effect of certain natural connectivity constraints on the parameterized complexity of two fundamental graph covering problems, namely and . Specifically, we impose the additional requirement that each connected component of a solution have at least vertices (resp. edges from the solution) for a fixed positive integer , and call the problem - (resp. - ). In both cases the parameter is the size of the solution. We show that These results significantly improve earlier work on these problems. We illustrate the utility of the technique used to solve - , by applying it to derive an -time FPT algorithm for the - problem. Our no-poly-kernel result for...
  • Idioma: Inglês

Buscando em bases de dados remotas. Favor aguardar.