Deeper Local Search for Better Approximation on Maximum Internal Spanning Trees

DOI10.1007/978-3-662-44777-2_53zbMath1425.68317OpenAlexW2096147380MaRDI QIDQ2921450

Jianxin Wang, Wenjun Li, Jian'er 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 theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (8)

A 2k-vertex Kernel for Maximum Internal Spanning Tree ⋮ 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 ⋮ An approximation algorithm for maximum internal spanning tree ⋮ Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree ⋮ Approximation algorithms for the maximum weight internal spanning tree problem

This page was built for publication: Deeper Local Search for Better Approximation on Maximum Internal Spanning Trees