An exact exponential-time algorithm for the directed maximum leaf spanning tree problem

DOI10.1016/j.jda.2012.03.006zbMath1247.05233OpenAlexW2027522856MaRDI QIDQ450578

Henning Fernau, Daniel Binkele-Raible

Publication date: 13 September 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2012.03.006

zbMATH Keywords

directed maximum leaf spanning tree problemexact exponential-time algorithmsNP-hard problems on directed graphsoutbranching with a maximum number of leaves

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (5)

Distributed Consensus for Multiagent Systems via Directed Spanning Tree Based Adaptive Control ⋮ Consensus of nonlinear multi-agent systems with directed switching graphs: a directed spanning tree based error system approach ⋮ A 2-approximation algorithm for finding a spanning tree with maximum number of leaves ⋮ Observer-based consensus for multi-agent systems with partial adaptive dynamic protocols ⋮ Efficient Local Search based on Dynamic Connectivity Maintenance for Minimum Connected Dominating Set

Cites Work

• Unnamed Item
• Unnamed Item
• Exact exponential algorithms.
• Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
• A new algorithm for finding trees with many leaves
• An exact algorithm for the maximum leaf spanning tree problem
• Parameterized algorithms for feedback set problems and their duals in tournaments
• FPT algorithms and kernels for the directed \(k\)-leaf problem
• Solving connected dominating set faster than \(2^n\)
• Dominating sets in directed graphs
• Tight bounds and a fast FPT algorithm for directed Max-Leaf Spanning Tree
• An Amortized Search Tree Analysis for k-Leaf Spanning Tree
• A measure & conquer approach for the analysis of exact algorithms
• A Parameterized Route to Exact Puzzles: Breaking the 2 n -Barrier for Irredundance
• A Faster Exact Algorithm for the Directed Maximum Leaf Spanning Tree Problem
• On Finding Directed Trees with Many Leaves
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
• Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
• Dominating Set and Converse Dominating Set of a Directed Graph

This page was built for publication: An exact exponential-time algorithm for the directed maximum leaf spanning tree problem