A 2k-vertex Kernel for Maximum Internal Spanning Tree

DOI10.1007/978-3-319-21840-3_41zbMath1451.68206arXiv1412.8296OpenAlexW1810979759MaRDI QIDQ3449846

Jianxin Wang, Wenjun Li, Yixin Cao, Jian'er Chen

Publication date: 30 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.8296

zbMATH Keywords

local searchparameterized computationkernelization algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (13)

Spotting Trees with Few Leaves ⋮ Spotting Trees with Few Leaves ⋮ Mixing Color Coding-Related Techniques ⋮ A simple linear time algorithm to solve the MIST problem on interval graphs ⋮ Reoptimization of parameterized problems ⋮ Representative families: a unified tradeoff-based approach ⋮ Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs ⋮ An approximation algorithm for maximum internal spanning tree ⋮ Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs ⋮ Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree ⋮ Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs ⋮ Approximation algorithms for the maximum weight internal spanning tree problem ⋮ Algorithms for maximum internal spanning tree problem for some graph classes

Cites Work

• Unnamed Item
• On the minimum diameter spanning tree problem
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
• Approximating the maximum internal spanning tree problem
• Minimum leaf out-branching and related problems
• A linear vertex kernel for maximum internal spanning tree
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• On finding spanning trees with few leaves
• Sharp separation and applications to exact and parameterized algorithms
• Deeper Local Search for Better Approximation on Maximum Internal Spanning Trees
• Representative Families: A Unified Tradeoff-Based Approach
• A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
• Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
• Dynamic Scaling of Growing Interfaces
• Limits and Applications of Group Algebras for Parameterized Problems
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• A randomized linear-time algorithm to find minimum spanning trees
• Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
• Algorithms and Data Structures

This page was built for publication: A 2k-vertex Kernel for Maximum Internal Spanning Tree