Leafy spanning arborescences in DAGs
From MaRDI portal
Publication:5970768
DOI10.1016/j.dam.2021.06.018OpenAlexW3180187830MaRDI QIDQ5970768
Cristina G. Fernandes, Carla Negri Lintzmayer
Publication date: 2 November 2022
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2021.06.018
approximation algorithmsdirected acyclic graphsmaximum leaf spanning arborescencemaximum leaf weighted spanning arborescence
Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- A 2-approximation algorithm for finding a spanning tree with maximum number of leaves
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Directed tree-width
- Approximation Algorithms for the Maximum Leaf Spanning Tree Problem on Acyclic Digraphs
- Kernel(s) for problems with no kernel
- Approximating the $$k$$-Set Packing Problem by Local Improvements
- A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
- On Finding Directed Trees with Many Leaves
- Approximating Maximum Leaf Spanning Trees in Almost Linear Time
- Spanning Directed Trees with Many Leaves
- Paths, Trees, and Flowers
- 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: Leafy spanning arborescences in DAGs
