Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem

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

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68W25: Approximation algorithms

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