Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems
From MaRDI portal
Publication:2839214
DOI10.1016/j.endm.2009.02.011zbMath1267.05260OpenAlexW1971373505MaRDI QIDQ2839214
Publication date: 4 July 2013
Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.endm.2009.02.011
Related Items
Improved bounds for spanning trees with many leaves, Spanning 3-ended trees in almost claw-free graphs, The existence of spanning ended system on claw-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Arbres avec un nombre maximum de sommets pendants
- Approximation hardness of dominating set problems in bounded degree graphs
- On complexity of minimum leaf out-branching 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
- On the approximability of some Maximum Spanning Tree Problems
- Directed tree-width
- Parametrized complexity theory.
- An approximation algorithm for the maximum leaf spanning arborescence problem
- Kernel(s) for problems with no kernel
- Minimum Leaf Out-Branching Problems
- On Problems without Polynomial Kernels (Extended Abstract)
- Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree
- A New Algorithm for Finding Trees with Many Leaves
- Approximating Maximum Leaf Spanning Trees in Almost Linear Time
- Approximation algorithms for connected dominating sets
- Spanning Directed Trees with Many Leaves
- Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem
- Parameterized Algorithms for Directed Maximum Leaf Problems
- Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
- Better Algorithms and Bounds for Directed Maximum Leaf Problems
- Digraphs
- Algorithms and Data Structures
