An exact algorithm for the maximum leaf spanning tree problem

DOI10.1016/J.TCS.2011.07.011zbMATH Open1233.68236DBLPjournals/tcs/FernauKKLLRR11OpenAlexW2180968341WikidataQ59442095 ScholiaQ59442095MaRDI QIDQ653320FDOQ653320

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

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

Recommendations

• An exact algorithm for the maximum leaf spanning tree problem
• An exact exponential-time algorithm for the directed maximum leaf spanning tree problem
• A faster exact algorithm for the directed maximum leaf spanning tree problem
• An exact algorithm for the maximum leaf spanning tree problem.
• An amortized search tree analysis for \(k\)-leaf spanning tree

zbMATH Keywords

graph algorithmsmaximum leaf spanning treespanning treeexponential time algorithms

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (24)

• Title not available (Why is that?)
• Complexity of the maximum leaf spanning tree problem on planar and regular graphs
• Title not available (Why is that?)
• Efficient Local Search based on Dynamic Connectivity Maintenance for Minimum Connected Dominating Set
• An exact algorithm for the maximum leaf spanning tree problem
• Kernelization for maximum leaf spanning tree with positive vertex weights
• Regenerator location problem: polyhedral study and effective branch-and-cut algorithms
• An exact exponential-time algorithm for the directed maximum leaf spanning tree problem
• On connected dominating sets of restricted diameter
• Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights
• Below all subsets for minimal connected dominating set
• The \(k\)-leaf spanning tree problem admits a klam value of 39
• The \(k\)-leaf spanning tree problem admits a klam value of 39
• Reformulations and solution algorithms for the maximum leaf spanning tree problem
• An amortized search tree analysis for finding a \(k\)-leaf spanning tree in an undirected graph
• An amortized search tree analysis for \(k\)-leaf spanning tree
• A faster exact algorithm for the directed maximum leaf spanning tree problem
• Computing the differential of a graph: hardness, approximability and exact algorithms
• An exact algorithm for the maximum leaf spanning tree problem.
• Title not available (Why is that?)
• Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem
• A 2-approximation algorithm for finding a spanning tree with maximum number of leaves
• Inclusion/exclusion meets measure and conquer
• Robust Connectivity of Graphs on Surfaces

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q653320)