A 2-approximation algorithm for finding a spanning tree with maximum number of leaves
From MaRDI portal
Publication:513269
DOI10.1007/s00453-015-0080-0zbMath1359.68318OpenAlexW2274535290MaRDI QIDQ513269
Stefanie Lowski, Roberto Solis-Oba, Paul Bonsma
Publication date: 3 March 2017
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/11858/00-001M-0000-0014-7BD6-0
Related Items
The connected domination number of grids, Leafy spanning \(k\)-forests, Further results on the total monochromatic connectivity of graphs, A 3-approximation algorithm for the maximum leaf \(k\)-forest problem, A Simple 2-Approximation for Maximum-Leaf Spanning Tree, Connected domination in maximal outerplanar graphs, How heavy independent sets help to find arborescences with many leaves in DAGs, Efficient Local Search based on Dynamic Connectivity Maintenance for Minimum Connected Dominating Set, Leafy spanning arborescences in DAGs
Cites Work
- Unnamed Item
- Unnamed Item
- Improved bounds for spanning trees with many leaves
- Max-leaves spanning tree is APX-hard for cubic graphs
- An exact exponential-time algorithm for the directed maximum leaf spanning tree problem
- An exact algorithm for the maximum leaf spanning tree problem
- A greedy approximation for minimum connected dominating sets
- The complexity ecology of parameters: An illustration using bounded max leaf number
- Arbres avec un nombre maximum de sommets pendants
- FPT algorithms and kernels for the directed \(k\)-leaf problem
- Constructing full spanning trees 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
- Approximation algorithms for connected dominating sets
- A self-stabilizing 3-approximation for the maximum leaf spanning tree problem in arbitrary networks
- Approximation Algorithms for the Maximum Leaf Spanning Tree Problem on Acyclic Digraphs
- An approximation algorithm for the maximum leaf spanning arborescence problem
- Spanning trees with many leaves in cubic graphs
- Tight bounds and a fast FPT algorithm for directed Max-Leaf Spanning Tree
- Kernel(s) for problems with no kernel
- A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
- Spanning Trees with Many Leaves
- An Amortized Search Tree Analysis for k-Leaf Spanning Tree
- On Finding Directed Trees with Many Leaves
- On Linear Time Minor Tests with Depth-First Search
- Approximating Maximum Leaf Spanning Trees in Almost Linear Time
- The maximum-leaf spanning tree problem: Formulations and facets
- Spanning Directed Trees with Many Leaves
- Mathematical Foundations of Computer Science 2003
- A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs
- Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights
