Max-leaves spanning tree is APX-hard for cubic graphs

DOI10.1016/j.jda.2011.06.005zbMath1246.68121OpenAlexW2964217904MaRDI QIDQ414465

Paul Bonsma

Publication date: 11 May 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2011.06.005

zbMATH Keywords

approximation algorithmcubic graphAPX-hardmaximum leafminimum connected dominating set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Complexity of the maximum leaf spanning tree problem on planar and regular graphs ⋮ Optimization of wireless sensor networks deployment with coverage and connectivity constraints ⋮ The \(k\)-hop connected dominating set problem: hardness and polyhedra ⋮ Robust Connectivity of Graphs on Surfaces ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ The complexity of spanning tree problems involving graphical indices ⋮ A 2-approximation algorithm for finding a spanning tree with maximum number of leaves ⋮ Connected Domination

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A greedy approximation for minimum connected dominating sets
• Solving connected dominating set faster than \(2^n\)
• Optimization, approximation, and complexity classes
• Spanning trees in graphs of minimum degree 4 or 5
• Three short proofs in graph theory
• A short note on the approximability of the maximum leaves spanning tree problem
• Approximation algorithms for connected dominating sets
• Some APX-completeness results for cubic graphs
• Proof verification and the hardness of approximation problems
• Spanning Trees with Many Leaves
• Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree
• A New Algorithm for Finding Trees with Many Leaves
• On Finding Directed Trees with Many Leaves
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
• A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs
• Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms

This page was built for publication: Max-leaves spanning tree is APX-hard for cubic graphs