Better approximation algorithms for the maximum internal spanning tree problem

DOI10.1007/S00453-013-9827-7MaRDI QIDQ2350897zbMATH OpenOpenAlexFDO

Authors Martin Knauer, Joachim Spoerhase

Publication date 25 June 2015

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-013-9827-7

zbMATH Keywords

approximation algorithmspanning tree

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) 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

• A linear vertex kernel for maximum internal spanning tree
• A survey on algorithms for the maximum internal spanning tree and related problems
• Approximate Local Search in Combinatorial Optimization
• Approximating spanning trees with few branches
• Approximating the maximum internal spanning tree problem
• Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
• Exact and parameterized algorithms for \textsc{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

(15)

• Approximating the maximum internal spanning tree problem
• On residual approximation in solution extension problems
• An improved algorithm for the k-source maximum eccentricity spanning trees
• Algorithms for maximum internal spanning tree problem for some graph classes
• Scatter search for the minimum leaf spanning tree problem
• Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
• Complexity of independency and cliquy trees
• A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem
• Deeper local search for better approximation on maximum internal spanning trees
• Approximating the maximum internal spanning tree problem via a maximum path-cycle cover
• On Residual Approximation in Solution Extension Problems
• Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
• Approximation Algorithms for the Maximum Internal Spanning Tree Problem
• Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
• Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree

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