On Finding Directed Trees with Many Leaves

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

Mathematics Subject Classification ID

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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.
• An approximation algorithm for the maximum leaf spanning arborescence problem
• 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

This page was built for publication: On Finding Directed Trees with Many Leaves