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 (9)
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
- 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
- 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
This page was built for publication: A 2-approximation algorithm for finding a spanning tree with maximum number of leaves
