skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices
Tipo de recurso Mostra resultados com: Mostra resultados com: Índice

On graph contractions and induced minors

van ’t Hof, Pim ; Kamiński, Marcin ; Paulusma, Daniël ; Szeider, Stefan ; Thilikos, Dimitrios M.

Discrete Applied Mathematics, 2012-04, Vol.160 (6), p.799-809 [Periódico revisado por pares]

Elsevier B.V

Texto completo disponível

Citações Citado por
  • Título:
    On graph contractions and induced minors
  • Autor: van ’t Hof, Pim ; Kamiński, Marcin ; Paulusma, Daniël ; Szeider, Stefan ; Thilikos, Dimitrios M.
  • Assuntos: Classification ; Complexity ; Computation ; Containment ; Graph contraction ; Graph induced minor ; Graph minor ; Graphs ; Integers ; Mathematical analysis ; Mathematical models
  • É parte de: Discrete Applied Mathematics, 2012-04, Vol.160 (6), p.799-809
  • Notas: ObjectType-Article-1
    SourceType-Scholarly Journals-1
    ObjectType-Feature-2
    content type line 23
  • Descrição: The Induced Minor Containment problem takes as input two graphs G and H, and asks whether G has H as an induced minor. We show that this problem is fixed parameter tractable in |VH| if G belongs to any nontrivial minor-closed graph class and H is a planar graph. For a fixed graph H, the H-Contractibility problem is to decide whether a graph can be contracted to H. The computational complexity classification of this problem is still open. So far, H has a dominating vertex in all cases known to be solvable in polynomial time, whereas H does not have such a vertex in all cases known to be NP-complete. Here, we present a class of graphs H with a dominating vertex for which H-Contractibility is NP-complete. We also present a new class of graphs H for which H-Contractibility can be solved in polynomial time. Finally, we study the (H,v)-Contractibility problem, where v is a vertex of H. The input of this problem is a graph G and an integer k, and the question is whether G is H-contractible such that the “bag” of G corresponding to v contains at least k vertices. We show that this problem is NP-complete whenever H is connected and v is not a dominating vertex of H.
  • Editor: Elsevier B.V
  • Idioma: Inglês
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.