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

DOI10.1016/J.JDA.2011.06.005MaRDI QIDQ414465zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(12)

• The k-hop connected dominating set problem: approximation and hardness
• 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

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)