An exact algorithm for the maximum leaf spanning tree problem

DOI10.1016/j.tcs.2011.07.011zbMath1233.68236OpenAlexW2180968341WikidataQ59442095 ScholiaQ59442095MaRDI QIDQ653320

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

Publication date: 9 January 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.07.011

zbMATH Keywords

spanning treegraph algorithmsmaximum leaf spanning treeexponential time algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (10)

Robust Connectivity of Graphs on Surfaces ⋮ Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem ⋮ An exact exponential-time algorithm for the directed maximum leaf spanning tree problem ⋮ Computing the differential of a graph: hardness, approximability and exact algorithms ⋮ A 2-approximation algorithm for finding a spanning tree with maximum number of leaves ⋮ Regenerator location problem: polyhedral study and effective branch-and-cut algorithms ⋮ Inclusion/exclusion meets measure and conquer ⋮ Below All Subsets for Minimal Connected Dominating Set ⋮ Efficient Local Search based on Dynamic Connectivity Maintenance for Minimum Connected Dominating Set ⋮ On connected dominating sets of restricted diameter

Cites Work

• Exact exponential algorithms.
• FPT algorithms and kernels for the directed \(k\)-leaf problem
• Solving connected dominating set faster than \(2^n\)
• Primal-dual algorithms for connected facility location problems
• A measure & conquer approach for the analysis of exact algorithms
• Simpler and better approximation algorithms for network design
• A New Algorithm for Finding Trees with Many Leaves
• An Exact Algorithm for the Maximum Leaf Spanning Tree Problem
• On Linear Time Minor Tests with Depth-First Search
• Mathematical Foundations of Computer Science 2003
• Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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