An approximation algorithm for maximum internal spanning tree

DOI10.1007/s10878-017-0245-7zbMath1418.90220arXiv1608.00196OpenAlexW2949714573MaRDI QIDQ1743498

Zhi-Zhong Chen, Lusheng Wang, Fei Guo, Youta Harada

Publication date: 13 April 2018

Published in: Journal of Combinatorial Optimization, WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1608.00196

zbMATH Keywords

graph algorithmsapproximation algorithmsspanning treespath-cycle covers

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items

Scatter search for the minimum leaf spanning tree problem, 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, 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

Cites Work

• Unnamed Item
• Unnamed Item
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
• 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
• Sharp separation and applications to exact and parameterized algorithms
• Deeper Local Search for Better Approximation on Maximum Internal Spanning Trees
• Approximating the Maximum Internal Spanning Tree Problem via a Maximum Path-Cycle Cover
• Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
• 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
• Algorithms and Data Structures
• Approximation algorithms for the maximum weight internal spanning tree problem