Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
From MaRDI portal
Publication:3183476
DOI10.1007/978-3-642-03367-4_40zbMath1253.68363MaRDI QIDQ3183476
Martin Knauer, Joachim Spoerhase
Publication date: 20 October 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-03367-4_40
Related Items
A Polynomial Time Algorithm for Finding a Spanning Tree with Maximum Number of Internal Vertices on Interval Graphs, Approximation algorithms for the maximum weight internal spanning tree problem, An approximation algorithm for maximum internal spanning tree, Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}, A simple linear time algorithm to solve the MIST problem on interval graphs, Approximating spanning trees with few branches, Better approximation algorithms for the maximum internal spanning tree problem, A multivariate framework for weighted FPT algorithms, Solving the maximum internal spanning tree problem on interval graphs in polynomial time, Unnamed Item, A 2k-vertex Kernel for Maximum Internal Spanning Tree, A Multivariate Approach for Weighted FPT Algorithms
Cites Work
- Unnamed Item
- Approximating the maximum internal spanning tree problem
- On finding spanning trees with few leaves
- Neighborhood unions and extremal spanning trees
- Approximation Algorithms for the Maximum Internal Spanning Tree Problem
- Approximate Local Search in Combinatorial Optimization
- Exact and Parameterized Algorithms for Max Internal Spanning Tree
- Algorithms and Data Structures