scientific article; zbMATH DE number 2080206

MaRDI QIDQ4472448zbMATH OpenFDO

Authors Michael R. Fellows, Catherine McCartin, Frances Rosamond, Ulrike Stege

Publication date 4 August 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/1974/19740240.htm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorics on words (68R15)

Recommendations

• Mathematical Foundations of Computer Science 2003
• An exact algorithm for the maximum leaf spanning tree problem
• An exact algorithm for the maximum leaf spanning tree problem
• FPT algorithms and kernels for the directed k-leaf problem
• Algorithms and Data Structures

Cited in

(19)

• Vertex and edge covers with clustering properties: Complexity and algorithms
• The \(k\)-leaf spanning tree problem admits a klam value of 39
• Constructing a spanning tree with many leaves
• Sources of complexity in subset choice
• Out-branchings with maximal number of leaves or internal vertices: algorithmic results and open problems
• Parameterized complexity: the main ideas and connections to practical computing
• The Impact of Parameterized Complexity to Interdisciplinary Problem Solving
• Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree
• Improved kernel results for some FPT problems based on simple observations
• Better Algorithms and Bounds for Directed Maximum Leaf Problems
• Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights
• A new algorithm for finding trees with many leaves
• An exact algorithm for the maximum leaf spanning tree problem
• Kernelization for finding lineal topologies (depth-first spanning trees) with many or few leaves
• Polynomial formulations as a barrier for reduction-based hardness proofs
• On the parameterized complexity of lineal topologies (depth-first spanning trees) with many or few leaves
• Breadth-first search trees with many or few leaves
• Looking at the stars
• FPT algorithms and kernels for the directed k-leaf problem

This page was built for publication:

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