On Finding Directed Trees with Many Leaves
From MaRDI portal
Publication:3656853
DOI10.1007/978-3-642-11269-0_7zbMath1273.68162arXiv0904.2658OpenAlexW1615046544MaRDI QIDQ3656853
Jean Daligault, Steéphan Thomassé
Publication date: 14 January 2010
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0904.2658
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
Related Items (16)
Leafy spanning \(k\)-forests ⋮ Reoptimization of parameterized problems ⋮ Linear kernels for outbranching problems in sparse digraphs ⋮ On maximum leaf trees and connections to connected maximum cut problems ⋮ Beyond bidimensionality: parameterized subexponential algorithms on directed graphs ⋮ Max-leaves spanning tree is APX-hard for cubic graphs ⋮ How heavy independent sets help to find arborescences with many leaves in DAGs ⋮ An exact exponential-time algorithm for the directed maximum leaf spanning tree problem ⋮ On the directed full degree spanning tree problem ⋮ A new algorithm for finding trees with many leaves ⋮ A 2-approximation algorithm for finding a spanning tree with maximum number of leaves ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ Basic Terminology, Notation and Results ⋮ Acyclic Digraphs ⋮ Leafy spanning arborescences in DAGs ⋮ A linear-time kernelization for the rooted \(k\)-leaf outbranching problem
Cites Work
- FPT algorithms and kernels for the directed \(k\)-leaf problem
- Solving connected dominating set faster than \(2^n\)
- Rubber bands, convex embeddings and graph connectivity
- Constructing full spanning trees for cubic graphs
- A short note on the approximability of the maximum leaves spanning tree problem
- Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity
- Parametrized complexity theory.
- On Problems without Polynomial Kernels (Extended Abstract)
- A New Algorithm for Finding Trees with Many Leaves
- Self-stabilizing systems in spite of distributed control
- Spanning Directed Trees with Many Leaves
- Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
- Parameterized Algorithms for Directed Maximum Leaf Problems
- Spanning trees with many leaves
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On Finding Directed Trees with Many Leaves
