A Simple 2-Approximation for Maximum-Leaf Spanning Tree

DOI10.1142/S0129054123420029MaRDI QIDQ6066463zbMATH OpenOpenAlexFDO

Authors Hsueh-I Lu

Publication date 16 November 2023

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2303.03125

zbMATH Keywords

approximation algorithmsmaximum-leaf spanning tree

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Abstract: For an $m$-edge connected simple graph $G$, finding a spanning tree of $G$ with the maximum number of leaves is MAXSNP-complete. The problem remains NP-complete even if $G$ is planar and the maximal degree of $G$ is at most four. Lu and Ravi gave the first known polynomial-time approximation algorithms with approximation factors $5$ and $3$. Later, they obtained a $3$-approximation algorithm that runs in near-linear time. The best known result is Solis-Oba, Bonsma, and Lowski's $O(m)$-time $2$-approximation algorithm. We show an alternative simple $O(m)$-time $2$-approximation algorithm whose analysis is simpler. This paper is dedicated to the cherished memory of our dear friend, Professor Takao Nishizeki.

Cites work

• A 2-approximation algorithm for finding a spanning tree with maximum number of leaves
• A linear-time algorithm to find four independent spanning trees in four connected planar graphs
• A short note on the approximability of the maximum leaves spanning tree problem
• An algorithm for finding a short closed spanning walk in a graph
• An approximation algorithm for the Hamiltonian walk problem on maximal planar graphs
• An Approximation Algorithm for the Maximum Independent Set Problem on Planar Graphs
• Approximability of partitioning graphs with supply and demand
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• Arbres avec un nombre maximum de sommets pendants
• CANONICAL DECOMPOSITION, REALIZER, SCHNYDER LABELING AND ORDERLY SPANNING TREES OF PLANE GRAPHS
• Constructing full spanning trees for cubic graphs
• Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs
• scientific article; zbMATH DE number 3742629 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305098 (Why is no real title available?)
• Improved bounds for spanning trees with many leaves
• On Linear Time Minor Tests with Depth-First Search
• On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Reconfiguration of Spanning Trees with Many or Few Leaves
• Self-stabilizing systems in spite of distributed control
• Spanning distribution trees of graphs (extended abstract)
• Spanning Trees with Many Leaves
• Spanning trees with many leaves
• Spanning trees with many leaves in cubic graphs

Cited in

(1)

• Knapsack problems with monotonically non-decreasing variable weights (profits) of items

This page was built for publication: A Simple 2-Approximation for Maximum-Leaf Spanning Tree

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