Approximating the Maximum Internal Spanning Tree Problem via a Maximum Path-Cycle Cover

DOI10.1007/978-3-319-13075-0_37zbMath1432.68361OpenAlexW231332773MaRDI QIDQ2942652

Daming Zhu, Xingfu Li

Publication date: 11 September 2015

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-13075-0_37

zbMATH Keywords

complexityapproximationmaximum internal spanning tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Related Items (10)

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 \(\frac{4}{3}\)-approximation algorithm 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 ⋮ An approximation algorithm for maximum internal spanning tree ⋮ 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 ⋮ Approximation algorithms for the maximum weight internal spanning tree problem ⋮ Algorithms for maximum internal spanning tree problem for some graph classes

This page was built for publication: Approximating the Maximum Internal Spanning Tree Problem via a Maximum Path-Cycle Cover