Better approximation algorithms for the maximum internal spanning tree problem

DOI10.1007/s00453-013-9827-7zbMath1325.68256OpenAlexW1985049677MaRDI QIDQ2350897

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 theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

On residual approximation in solution extension problems ⋮ Scatter search for the minimum leaf spanning tree problem ⋮ A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem ⋮ On Residual Approximation in Solution Extension Problems ⋮ Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs ⋮ Complexity of independency and cliquy trees ⋮ Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree ⋮ Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs ⋮ Algorithms for maximum internal spanning tree problem for some graph classes

Cites Work

• Unnamed Item
• Unnamed Item
• Approximating the maximum internal spanning tree problem
• A linear vertex kernel for maximum internal spanning tree
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• On finding spanning trees with few leaves
• Neighborhood unions and extremal spanning trees
• Approximating Spanning Trees with Few Branches
• Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
• Approximate Local Search in Combinatorial Optimization

This page was built for publication: Better approximation algorithms for the maximum internal spanning tree problem