A Simple 2-Approximation for Maximum-Leaf Spanning Tree
From MaRDI portal
Publication:6066463
DOI10.1142/s0129054123420029arXiv2303.03125OpenAlexW4378652732MaRDI QIDQ6066463
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
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved bounds for spanning trees with many leaves
- A 2-approximation algorithm for finding a spanning tree with maximum number of leaves
- Arbres avec un nombre maximum de sommets pendants
- Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs
- Approximability of partitioning graphs with supply and demand
- Constructing full spanning trees for cubic graphs
- A short note on the approximability of the maximum leaves spanning tree problem
- An approximation algorithm for the Hamiltonian walk problem on maximal planar graphs
- Spanning trees with many leaves in cubic graphs
- Proof verification and the hardness of approximation problems
- Spanning Trees with Many Leaves
- Probabilistic checking of proofs
- An algorithm for finding a short closed spanning walk in a graph
- An Approximation Algorithm for the Maximum Independent Set Problem on Planar Graphs
- On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
- On Linear Time Minor Tests with Depth-First Search
- Self-stabilizing systems in spite of distributed control
- Approximating Maximum Leaf Spanning Trees in Almost Linear Time
- CANONICAL DECOMPOSITION, REALIZER, SCHNYDER LABELING AND ORDERLY SPANNING TREES OF PLANE GRAPHS
- A LINEAR-TIME ALGORITHM TO FIND FOUR INDEPENDENT SPANNING TREES IN FOUR CONNECTED PLANAR GRAPHS
- Spanning Distribution Trees of Graphs
- Reconfiguration of Spanning Trees with Many or Few Leaves
- Spanning trees with many leaves
This page was built for publication: A Simple 2-Approximation for Maximum-Leaf Spanning Tree
