Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem

DOI10.1007/978-3-642-03367-4_40zbMath1253.68363OpenAlexW1513252978MaRDI 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

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (12)

A 2k-vertex Kernel for Maximum Internal Spanning Tree ⋮ A Multivariate Approach for Weighted FPT Algorithms ⋮ Solving the maximum internal spanning tree problem on interval graphs in polynomial time ⋮ A simple linear time algorithm to solve the MIST problem on interval graphs ⋮ A multivariate framework for weighted FPT algorithms ⋮ Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree} ⋮ A Polynomial Time Algorithm for Finding a Spanning Tree with Maximum Number of Internal Vertices on Interval Graphs ⋮ An approximation algorithm for maximum internal spanning tree ⋮ Unnamed Item ⋮ Approximation algorithms for the maximum weight internal spanning tree problem ⋮ Approximating spanning trees with few branches ⋮ Better approximation algorithms for the maximum internal spanning tree problem

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

This page was built for publication: Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem