A Linear Vertex Kernel for Maximum Internal Spanning Tree - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

A Linear Vertex Kernel for Maximum Internal Spanning Tree

Fedor V. Fomin
Serge Gaspers
  • Fonction : Auteur
  • PersonId : 936216
Saket Saurabh
Stéphan Thomassé

Résumé

We present a polynomial time algorithm that for any graph G and integer k either finds a spanning tree with at least k internal vertices, or outputs a new graph G' on at most 3k vertices and an integer k' such that G' has a spanning tree with at least k internal vertices if and only if G' has a spanning tree with at least k' internal vertices. In other words, we show that the Maximum Internal Spanning Tree problem parameterized by the number of internal vertices k, has a 3k-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 H contains a hypertree if and only if H is partition connected."
Fichier non déposé

Dates et versions

lirmm-00432674 , version 1 (16-11-2009)

Identifiants

  • HAL Id : lirmm-00432674 , version 1

Citer

Fedor V. Fomin, Serge Gaspers, Saket Saurabh, Stéphan Thomassé. A Linear Vertex Kernel for Maximum Internal Spanning Tree. ISAAC'09: 20th International Symposium on Algorithms and Computation, pp.9. ⟨lirmm-00432674⟩
92 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More