کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429561 | 687602 | 2013 | 6 صفحه PDF | دانلود رایگان |
We present a polynomial time algorithm that for any graph G and integer k⩾0k⩾0, either finds a spanning tree with at least k internal vertices, or outputs a new graph GRGR on at most 3k vertices and an integer k′k′ such that G has a spanning tree with at least k internal vertices if and only if GRGR has a spanning tree with at least k′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.”
► First linear kernel for Maximum Internal Spanning Tree.
► Uses a classical min–max result about hypertrees by Frank et al. (2003) [6].
► Shows another application of the c-expansion lemma of Thomassé (2010) [16].
Journal: Journal of Computer and System Sciences - Volume 79, Issue 1, February 2013, Pages 1–6