skip to main content
Idioma:

Subexponential algorithms for partial cover problems

Fomin, Fedor V ; Lokshtanov, Daniel ; Raman, Venkatesh ; Saurabh, Saket

Information Processing Letters, 2011, Vol.111(16), pp.814-818 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por
  • Título:
    Subexponential algorithms for partial cover problems
  • Autor: Fomin, Fedor V ; Lokshtanov, Daniel ; Raman, Venkatesh ; Saurabh, Saket
  • Assuntos: Graph Algorithms ; Parameterized Algorithms ; Subexponential Algorithms ; Partial Cover Problems ; Partial Dominating Set ; Computer Science
  • É parte de: Information Processing Letters, 2011, Vol.111(16), pp.814-818
  • Descrição: Partial Cover problems are optimization versions of fundamental and well-studied problems like and . Here one is interested in covering (or dominating) the maximum number of edges (or vertices) using a given number of vertices, rather than covering all edges (or vertices). In general graphs, these problems are hard for parameterized complexity classes when parameterized by . It was recently shown by Amini et al. (2008) that and are fixed parameter tractable on large classes of sparse graphs, namely -minor-free graphs, which include planar graphs and graphs of bounded genus. In particular, it was shown that on planar graphs both problems can be solved in time . During the last decade there has been an extensive study on parameterized subexponential algorithms. In particular, it was shown that the classical and problems can be solved in subexponential time on -minor-free graphs. The techniques developed to obtain subexponential algorithms for classical problems do not apply to partial cover problems. It was left as an open problem by Amini et al. (2008) whether there is a subexponential algorithm for and . In this paper, we answer the question affirmatively by solving both problems in time not only on planar graphs but also on much larger classes of graphs, namely, apex-minor-free graphs. Compared to previously known algorithms for these problems our algorithms are significantly faster and simpler. ► First parameterized subexponential time algorithm for partial cover problems. ► Includes problems like and . ► Works for planar and apex-minor-free graphs.
  • Idioma: Inglês
Links
Voltar para lista de resultados

  • Realização: USP

Buscando em bases de dados remotas. Favor aguardar.