Max-leaves spanning tree is APX-hard for cubic graphs
type: Item
instance of: scholarly article
title: Max-leaves spanning tree is APX-hard for cubic graphs
zbMATH Open document ID: 1246.68121
author: Paul Bonsma
published in: Journal of Discrete Algorithms
publication date: 2012-05-11T00:00:00Z
review text: MaxLeaf is the problem of finding a spanning tree with a maximum number of leaves in a connected graph. \textit{R. Solis-Oba} [Lect.\ Notes Comput. Sci. 1461, 441--452 (1998; Zbl 0932.68069)] presented a 2-approximation algorithm for MaxLeaf. \textit{P. Bonsma} and \textit{F. Zickfeld} [SIAM J.\ Discrete Math.\ 25, No.\ 4, 1652--1666 (2011; Zbl 1237.05041)] gave a 3/2-approximation algorithm for the restriction to cubic graphs. \textit{G. Galbiati}, \textit{F. Maffioli} and \textit{A. Morzenti} [Inf. Process. Lett. 52, No. 1, 45--49 (1994; Zbl 0942.68647)] showed that MaxLeaf is APX-hard in general. Here the author shows that MaxLeaf is also APX-hard for cubic graphs, and so is the related problem Minimum Connected Dominating Set when restricted to cubic graphs.
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6033184
zbMATH Keywords: maximum leaf
zbMATH Keywords: minimum connected dominating set
zbMATH Keywords: APX-hard
zbMATH Keywords: approximation algorithm
zbMATH Keywords: cubic graph
MaRDI profile type: Publication
full work available at URL: j.jda.2011.06.005
OpenAlex ID: W2964217904
cites work: Some APX-completeness results for cubic graphs
cites work: Proof verification and the hardness of approximation problems
cites work: Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree
cites work: A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
cites work: Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
cites work: A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs
cites work: On Finding Directed Trees with Many Leaves
cites work: Q4342632
cites work: An approximation algorithm for the maximum leaf spanning arborescence problem
cites work: Solving connected dominating set faster than \(2^n\)
cites work: A short note on the approximability of the maximum leaves spanning tree problem
cites work: Spanning trees in graphs of minimum degree 4 or 5
cites work: Approximation algorithms for connected dominating sets
cites work: Spanning Trees with Many Leaves
cites work: A New Algorithm for Finding Trees with Many Leaves
cites work: Q4411401
cites work: Three short proofs in graph theory
cites work: Approximating Maximum Leaf Spanning Trees in Almost Linear Time
cites work: Optimization, approximation, and complexity classes
cites work: A greedy approximation for minimum connected dominating sets
cites work: Q4252040
DOI: 10.1016/J.JDA.2011.06.005
description: scientific article; zbMATH DE number 6033184