An approximation algorithm for maximum internal spanning tree
From MaRDI portal
Publication:1743498
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
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