A 2k-vertex Kernel for Maximum Internal Spanning Tree
From MaRDI portal
Publication:3449846
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
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
