A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs

DOI10.1137/100801251zbMath1237.05041OpenAlexW2016241195MaRDI QIDQ3225144

Paul Bonsma, Florian Zickfeld

Publication date: 15 March 2012

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/883563acaf3b011d7291426db89a4220cd88bc7c

zbMATH Keywords

approximation algorithmspanning treecubic graphconnected dominating setmaximum leaf

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (5)

Further results on the total monochromatic connectivity of graphs ⋮ Robust Connectivity of Graphs on Surfaces ⋮ Improved bounds for spanning trees with many leaves ⋮ A 2-approximation algorithm for finding a spanning tree with maximum number of leaves ⋮ Leafy spanning arborescences in DAGs

This page was built for publication: A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs