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

DOI10.1016/J.JDA.2011.06.005zbMATH Open1246.68121OpenAlexW2964217904MaRDI QIDQ414465FDOQ414465

Authors: 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

Recommendations

• A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs
• A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
• A 3/2-approximation algorithm for finding spanning trees with many leaves in cubic graphs
• scientific article; zbMATH DE number 1947432
• Complexity of the maximum leaf spanning tree problem on planar and regular graphs

zbMATH Keywords

approximation algorithmcubic graphAPX-hardmaximum leafminimum connected dominating set

Mathematics Subject Classification ID

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

Cites Work

• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• Spanning trees in graphs of minimum degree 4 or 5
• A short note on the approximability of the maximum leaves spanning tree problem
• An approximation algorithm for the maximum leaf spanning arborescence problem
• Proof verification and the hardness of approximation problems
• Spanning Trees with Many Leaves
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Three short proofs in graph theory
• Approximation algorithms for connected dominating sets
• A greedy approximation for minimum connected dominating sets
• Solving connected dominating set faster than \(2^n\)
• On finding directed trees with many leaves
• Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
• Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree
• A New Algorithm for Finding Trees with Many Leaves

Cited In (12)

• Complexity of the maximum leaf spanning tree problem on planar and regular graphs
• A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs
• Some APX-completeness results for cubic graphs
• Robust connectivity of graphs on surfaces
• A 3/2-approximation algorithm for finding spanning trees with many leaves in cubic graphs
• The \(k\)-hop connected dominating set problem: hardness and polyhedra
• Optimization of wireless sensor networks deployment with coverage and connectivity constraints
• The complexity of spanning tree problems involving graphical indices
• A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
• A 2-approximation algorithm for finding a spanning tree with maximum number of leaves
• Connected domination
• The \(k\)-hop connected dominating set problem: approximation and hardness

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414465)