Approximating the maximum internal spanning tree problem via a maximum path-cycle cover

DOI10.1007/978-3-319-13075-0_37MaRDI QIDQ2942652zbMATH OpenOpenAlexFDO

Authors Xingfu Li, Daming Zhu

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

approximationcomplexitymaximum internal spanning tree

Mathematics Subject Classification ID

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

Recommendations

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

Cited in

(9)

• Algorithms for maximum internal spanning tree problem for some graph classes
• 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
• Solving the maximum internal spanning tree problem on interval graphs in polynomial time
• 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
• Algorithms and Data Structures
• Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree

This page was built for publication: Approximating the maximum internal spanning tree problem via a maximum path-cycle cover

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