Approximation Algorithms for the Maximum Leaf Spanning Tree Problem on Acyclic Digraphs
From MaRDI portal
Publication:2896380
DOI10.1007/978-3-642-29116-6_7zbMath1242.68372OpenAlexW221072716MaRDI QIDQ2896380
Nadine Schwartges, Alexander Wolff, Joachim Spoerhase
Publication date: 16 July 2012
Published in: Approximation and Online Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-29116-6_7
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)
Related Items
How heavy independent sets help to find arborescences with many leaves in DAGs ⋮ A 2-approximation algorithm for finding a spanning tree with maximum number of leaves ⋮ Acyclic Digraphs ⋮ Leafy spanning arborescences in DAGs
This page was built for publication: Approximation Algorithms for the Maximum Leaf Spanning Tree Problem on Acyclic Digraphs