Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem

DOI10.1007/978-3-642-03367-4_40MaRDI QIDQ3183476zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Better approximation algorithms for the maximum internal spanning tree problem
• Approximating the maximum internal spanning tree problem
• Approximation Algorithms for the Maximum Internal Spanning Tree Problem
• A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem

Cites work

• Algorithms and Data Structures
• Approximate Local Search in Combinatorial Optimization
• Approximating the maximum internal spanning tree problem
• Approximation Algorithms for the Maximum Internal Spanning Tree Problem
• Exact and parameterized algorithms for Max Internal Spanning Tree
• Neighborhood unions and extremal spanning trees
• On finding spanning trees with few leaves
• Reducing to independent set structure -- the case of k-internal spanning tree

Cited in

(16)

• Approximating the maximum internal spanning tree problem
• An improved algorithm for the k-source maximum eccentricity spanning trees
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• A simple linear time algorithm to solve the MIST problem on interval graphs
• Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free 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
• A survey on algorithms for the maximum internal spanning tree and related problems
• Deeper local search for better approximation on maximum internal spanning trees
• A 2k-vertex kernel for maximum internal spanning tree
• A multivariate approach for weighted FPT algorithms
• Approximation Algorithms for the Maximum Internal Spanning Tree Problem
• A polynomial time algorithm for finding a spanning tree with maximum number of internal vertices on interval graphs
• Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3183476)