An exact algorithm for the maximum leaf spanning tree problem
From MaRDI portal
Publication:653320
DOI10.1016/j.tcs.2011.07.011zbMath1233.68236WikidataQ59442095 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
Related Items
Below All Subsets for Minimal Connected Dominating Set, Efficient Local Search based on Dynamic Connectivity Maintenance for Minimum Connected Dominating Set, Robust Connectivity of Graphs on Surfaces, An exact exponential-time algorithm for the directed maximum leaf spanning tree problem, 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, On connected dominating sets of restricted diameter, Computing the differential of a graph: hardness, approximability and exact algorithms, Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
