Max-leaves spanning tree is APX-hard for cubic graphs (Q414465)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 6033184
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Max-leaves spanning tree is APX-hard for cubic graphs |
scientific article; zbMATH DE number 6033184 |
Statements
Max-leaves spanning tree is APX-hard for cubic graphs (English)
0 references
11 May 2012
0 references
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.
0 references
maximum leaf
0 references
minimum connected dominating set
0 references
APX-hard
0 references
approximation algorithm
0 references
cubic graph
0 references
0 references
0.8981676697731018
0 references
0.8907397389411926
0 references
0.8899510502815247
0 references
0.8524157404899597
0 references
