Fomin, Fedor V. ; Gaspers, Serge ; Saurabh, Saket ; Thomassé, Stéphan
(2009)
*A Linear Vertex Kernel for Maximum Internal Spanning Tree*
Lecture Notes in Computer Science, 5878
.
pp. 275-282.
ISSN 0302-9743

Full text not available from this repository.

Official URL: http://doi.org/10.1007/978-3-642-10631-6_29

Related URL: http://dx.doi.org/10.1007/978-3-642-10631-6_29

## Abstract

We present a polynomial time algorithm that for any graph G and integer k ≥ 0, either finds a spanning tree with at least k internal vertices, or outputs a new graph G R 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 R 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.”

Item Type: | Article |
---|---|

Source: | Copyright of this article belongs to Springer-Verlag. |

ID Code: | 123445 |

Deposited On: | 16 Sep 2021 12:04 |

Last Modified: | 16 Sep 2021 12:04 |

Repository Staff Only: item control page