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

DOI10.1016/j.jda.2012.03.006zbMath1247.05233MaRDI 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 problem; exact exponential-time algorithms; NP-hard problems on directed graphs; outbranching with a maximum number of leaves

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C20: Directed graphs (digraphs), tournaments