A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem
type: Item
instance of: scholarly article
title: A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem
zbMATH Open document ID: 1480.68013
author: Xingfu Li
author: Daming Zhu
author: Lusheng Wang
published in: Journal of Computer and System Sciences
publication date: 2021-03-10T00:00:00Z
review text: The problem is to find a spanning tree with maximal number of internal vertices in an undirected graph. It seems to have already earlier attracted some activity. Here, a 7-line verbally formulated algorithm is presented. It is based on a sequence of ideas to reduce the given graph. Performance ratios of \(\frac{4}{3}\) vs. \(\frac{3}{2}\) and others in the literature are discussed.
reviewed by: Gunther Schmidt
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 7319300
zbMATH Keywords: maximum internal spanning tree problem
zbMATH Keywords: approximation algorithm
zbMATH Keywords: performance ratio
MaRDI profile type: MaRDI publication profile
full work available at URL: j.jcss.2021.01.001
OpenAlex ID: W3119752030
cites work: Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
cites work: Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
cites work: Q5675543
cites work: Sharp separation and applications to exact and parameterized algorithms
cites work: A linear vertex kernel for maximum internal spanning tree
cites work: Q4198056
cites work: Better approximation algorithms for the maximum internal spanning tree problem
cites work: Deeper Local Search for Better Approximation on Maximum Internal Spanning Trees
cites work: Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree
cites work: Approximating the Maximum Internal Spanning Tree Problem via a Maximum Path-Cycle Cover
cites work: The Traveling Salesman Problem with Distances One and Two
cites work: Q3369936
cites work: Algorithms and Data Structures
cites work: Approximating the maximum internal spanning tree problem
cites work: On finding spanning trees with few leaves
cites work: Another look at the degree constrained subgraph problem
cites work: Algorithms for k-Internal Out-Branching
DOI: 10.1016/J.JCSS.2021.01.001
description: scientific article; zbMATH DE number 7319300