A 2k-vertex Kernel for Maximum Internal Spanning Tree
type: Item
instance of: scholarly article
title: A 2k-vertex Kernel for Maximum Internal Spanning Tree
zbMATH Open document ID: 1451.68206
DOI: 10.1007/978-3-319-21840-3_41
author: Wen-Jun Li
author: Jianxin Wang
author: Yixin Cao
author: Jianer Chen
published in: Lecture Notes in Computer Science
publication date: 2015-10-30T00:00:00Z
full work available at URL: https://arxiv.org/abs/1412.8296
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q27
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 6502377
zbMATH Keywords: parameterized computation
zbMATH Keywords: kernelization algorithms
zbMATH Keywords: local search
MaRDI profile type: Publication
OpenAlex ID: W1810979759
arXiv ID: 1412.8296
cites work: Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
cites work: Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
cites work: A linear vertex kernel for maximum internal spanning tree
cites work: Sharp separation and applications to exact and parameterized algorithms
cites work: Minimum leaf out-branching and related problems
cites work: On the minimum diameter spanning tree problem
cites work: A randomized linear-time algorithm to find minimum spanning trees
cites work: Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
cites work: A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
cites work: Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
cites work: Limits and Applications of Group Algebras for Parameterized Problems
cites work: Deeper Local Search for Better Approximation on Maximum Internal Spanning Trees
cites work: Approximating Maximum Leaf Spanning Trees in Almost Linear Time
cites work: Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
cites work: Dynamic Scaling of Growing Interfaces
cites work: Algorithms and Data Structures
cites work: Q3369936
cites work: Approximating the maximum internal spanning tree problem
cites work: On finding spanning trees with few leaves
cites work: Representative Families: A Unified Tradeoff-Based Approach
description: scientific article