An approximation algorithm for the maximum leaf spanning arborescence problem

DOI10.1145/1798596.1798599zbMath1300.68065OpenAlexW2083082533WikidataQ56502745 ScholiaQ56502745MaRDI QIDQ2930326

Adrian Vetta, Matthew Drescher

Publication date: 18 November 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://escholarship.mcgill.ca/concern/theses/3n204190p

zbMATH Keywords

directed graphsapproximation algorithmsarborescencemaximum leaf

Mathematics Subject Classification ID

Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (12)

FPT algorithms and kernels for the directed \(k\)-leaf problem ⋮ On maximum leaf trees and connections to connected maximum cut problems ⋮ Parameterized approximation via fidelity preserving transformations ⋮ Max-leaves spanning tree is APX-hard for cubic graphs ⋮ An exact exponential-time algorithm for the directed maximum leaf spanning tree problem ⋮ A new algorithm for finding trees with many leaves ⋮ Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree ⋮ A 2-approximation algorithm for finding a spanning tree with maximum number of leaves ⋮ Better Algorithms and Bounds for Directed Maximum Leaf Problems ⋮ Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems ⋮ On Finding Directed Trees with Many Leaves ⋮ A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs

This page was built for publication: An approximation algorithm for the maximum leaf spanning arborescence problem