An Exact Algorithm for the Maximum Leaf Spanning Tree Problem

DOI10.1007/978-3-642-11269-0_13zbMath1273.05219OpenAlexW2133106928MaRDI QIDQ3656859

Mathieu Liedloff, Dieter Kratsch, Henning Fernau, Daniel Raible, Joachim Kneis, Alexander Langer, Peter Rossmanith

Publication date: 14 January 2010

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-11269-0_13

zbMATH Keywords

branching algorithmConnected Dominating Set problemMaximum Leaf Spanning Tree problemMeasure-and-Conquer technique

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Spanning trees with a constraint on the number of leaves. A new formulation ⋮ Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree} ⋮ On independent sets and bicliques in graphs ⋮ An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set} ⋮ An exact algorithm for connected red-blue dominating set ⋮ An exact algorithm for the maximum leaf spanning tree problem

This page was built for publication: An Exact Algorithm for the Maximum Leaf Spanning Tree Problem