A Linear Vertex Kernel for Maximum Internal Spanning Tree

Details A Linear Vertex Kernel for Maximum Internal Spanning Tree A Linear Vertex Kernel for Maximum Internal Spanning Tree

2009-07-20

arxiv.org/abs/0907.3208v2

Computer Science

Data Structures and Algorithms

Scientific paper

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' 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."

Affiliated with

Also associated with

No associations

Rating

A Linear Vertex Kernel for Maximum Internal Spanning Tree does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Linear Vertex Kernel for Maximum Internal Spanning Tree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Linear Vertex Kernel for Maximum Internal Spanning Tree will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-695639