skip to main content

A linear vertex kernel for maximum internal spanning tree

Fomin, Fedor V ; Gaspers, Serge ; Saurabh, Saket ; Thomassé, Stéphan

Journal of Computer and System Sciences, February 2013, Vol.79(1), pp.1-6 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por
  • Título:
    A linear vertex kernel for maximum internal spanning tree
  • Autor: Fomin, Fedor V ; Gaspers, Serge ; Saurabh, Saket ; Thomassé, Stéphan
  • Assuntos: Algorithm ; Crown Decomposition ; Kernelization ; Parameterized Complexity ; Preprocessing ; Engineering ; Computer Science
  • É parte de: Journal of Computer and System Sciences, February 2013, Vol.79(1), pp.1-6
  • Descrição: We present a polynomial time algorithm that for any graph and integer , either finds a spanning tree with at least internal vertices, or outputs a new graph on at most 3 vertices and an integer such that has a spanning tree with at least internal vertices if and only if has a spanning tree with at least internal vertices. In other words, we show that the problem parameterized by the number of internal vertices has a 3 -vertex kernel. Our result is based on an innovative application of a classical min–max result about hypertrees in hypergraphs which states that “a hypergraph contains a hypertree if and only if is partition-connected.” ► First linear kernel...
  • Idioma: Inglês

Buscando em bases de dados remotas. Favor aguardar.