Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
type: Item
instance of: scholarly article
title: Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
zbMATH Open document ID: 1259.05159
author: Daniel Binkele-Raible
author: Henning Fernau
author: Serge Gaspers
author: Mathieu Liedloff
published in: Algorithmica
publication date: 2013-03-05T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 6141208
zbMATH Keywords: exact exponential-time algorithms
zbMATH Keywords: measure and conquer
zbMATH Keywords: parameterized algorithms
zbMATH Keywords: spanning tree problems
zbMATH Keywords: maximum internal spanning trees
MaRDI profile type: Publication
full work available at URL: s00453-011-9575-5
OpenAlex ID: W2058133856
cites work: Reverse search for enumeration
cites work: Dynamic Programming Treatment of the Travelling Salesman Problem
cites work: Enumerate and Measure: Improving Parameter Budget Management
cites work: Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
cites work: Fourier meets M\"{o}bius: fast subset convolution
cites work: Vertex cover: Further observations and further improvements
cites work: Improved upper bounds for vertex cover
cites work: Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
cites work: The Traveling Salesman Problem for Cubic Graphs
cites work: Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
cites work: Exact and Parameterized Algorithms for Max Internal Spanning Tree
cites work: An Exact Algorithm for the Maximum Leaf Spanning Tree Problem
cites work: On the minimum feedback vertex set problem: Exact and enumeration algorithms
cites work: A Linear Vertex Kernel for Maximum Internal Spanning Tree
cites work: A measure & conquer approach for the analysis of exact algorithms
cites work: Solving connected dominating set faster than \(2^n\)
cites work: Exact exponential algorithms.
cites work: Sharp Separation and Applications to Exact and Parameterized Algorithms
cites work: A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
cites work: A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
cites work: A Dynamic Programming Approach to Sequencing Problems
cites work: An Improved Exact Algorithm for Cubic Graph TSP
cites work: Dynamic programming meets the principle of inclusion and exclusion
cites work: Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
cites work: Saving space by algebraization
cites work: Even Faster Algorithm for Set Splitting!
cites work: On cliques in graphs
cites work: Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting
cites work: Spanning trees: A survey
cites work: Algorithms and Data Structures
cites work: Q3369936
cites work: An Amortized Search Tree Analysis for k-Leaf Spanning Tree
cites work: Algorithms for maximum independent sets
cites work: On finding spanning trees with few leaves
cites work: Approximating the maximum internal spanning tree problem
cites work: A survey on algorithms for the maximum internal spanning tree and related problems
cites work: Refined memorization for vertex cover
DOI: 10.1007/S00453-011-9575-5
description: scientific article; zbMATH DE number 6141208