Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}

DOI10.1007/s00453-011-9575-5zbMath1259.05159OpenAlexW2058133856MaRDI QIDQ1939668

Henning Fernau, Mathieu Liedloff, Serge Gaspers, Daniel Binkele-Raible

Publication date: 5 March 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9575-5

zbMATH Keywords

parameterized algorithmsmeasure and conquerexact exponential-time algorithmsspanning tree problemsmaximum internal spanning trees

Mathematics Subject Classification ID

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

Related Items

Spotting Trees with Few Leaves, On the number of connected sets in bounded degree graphs, Spotting Trees with Few Leaves, A 2k-vertex Kernel for Maximum Internal Spanning Tree, Mixing Color Coding-Related Techniques, Solving the maximum internal spanning tree problem on interval graphs in polynomial time, Scatter search for the minimum leaf spanning tree problem, Parameterized algorithms for non-separating trees and branchings in digraphs, A simple linear time algorithm to solve the MIST problem on interval graphs, A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem, A multivariate framework for weighted FPT algorithms, Exact Algorithms for the Minimum Load Spanning Tree Problem, The \(k\)-leaf spanning tree problem admits a klam value of 39, On the Number of Connected Sets in Bounded Degree Graphs, Representative families: a unified tradeoff-based approach, Leaf-Critical and Leaf-Stable Graphs, A Polynomial Time Algorithm for Finding a Spanning Tree with Maximum Number of Internal Vertices on Interval Graphs, Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs, An approximation algorithm for maximum internal spanning tree, Depth first search in claw-free graphs, Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs, Complexity of independency and cliquy trees, Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree, Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs, Approximation algorithms for the maximum weight internal spanning tree problem, Exact algorithms for counting 3-colorings of graphs, Algorithms for maximum internal spanning tree problem for some graph classes, Better approximation algorithms for the maximum internal spanning tree problem

Cites Work

• Unnamed Item
• Unnamed Item
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Exact exponential algorithms.
• Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
• Spanning trees: A survey
• Improved upper bounds for vertex cover
• Refined memorization for vertex cover
• Solving connected dominating set faster than \(2^n\)
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
• Approximating the maximum internal spanning tree problem
• Dynamic programming meets the principle of inclusion and exclusion
• Reverse search for enumeration
• On finding spanning trees with few leaves
• Vertex Cover: Further Observations and Further Improvements
• Saving space by algebraization
• Enumerate and Measure: Improving Parameter Budget Management
• Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting
• Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
• Dynamic Programming Treatment of the Travelling Salesman Problem
• A Dynamic Programming Approach to Sequencing Problems
• An Amortized Search Tree Analysis for k-Leaf Spanning Tree
• A measure & conquer approach for the analysis of exact algorithms
• A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
• Fourier meets M\"{o}bius: fast subset convolution
• Sharp Separation and Applications to Exact and Parameterized Algorithms
• An Improved Exact Algorithm for Cubic Graph TSP
• Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
• A Linear Vertex Kernel for Maximum Internal Spanning Tree
• An Exact Algorithm for the Maximum Leaf Spanning Tree Problem
• Even Faster Algorithm for Set Splitting!
• Algorithms for maximum independent sets
• The Traveling Salesman Problem for Cubic Graphs
• Exact and Parameterized Algorithms for Max Internal Spanning Tree
• Algorithms and Data Structures
• On cliques in graphs