Deeper local search for better approximation on maximum internal spanning trees

DOI10.1007/978-3-662-44777-2_53MaRDI QIDQ2921450zbMATH OpenOpenAlexFDO

Authors Wen-Jun Li, Jianxin Wang, Jianer Chen

Publication date 8 October 2014

Published in Algorithms - ESA 2014 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-44777-2_53

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

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

Cited in

(7)

• A simple linear time algorithm to solve the MIST problem on interval 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
• Finding good tree decompositions by local search
• A 2k-vertex kernel for maximum internal spanning tree
• A polynomial time algorithm for finding a spanning tree with maximum number of internal vertices on interval graphs
• Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree

This page was built for publication: Deeper local search for better approximation on maximum internal spanning trees

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