A linear vertex kernel for maximum internal spanning tree

DOI10.1016/j.jcss.2012.03.004zbMath1258.05117OpenAlexW1822472214WikidataQ60488411 ScholiaQ60488411MaRDI QIDQ1936242

Fedor V. Fomin, Serge Gaspers, Saket Saurabh, Steéphan Thomassé

Publication date: 21 February 2013

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2012.03.004

zbMATH Keywords

polynomial time algorithmhypergraphsparameterized complexitykernelizationpreprocessinghypertreescrown decompositionmin-max resultspartition connected hypergraphs

Mathematics Subject Classification ID

Trees (05C05) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (22)

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 ⋮ 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 ⋮ Reoptimization of parameterized problems ⋮ Representative families: a unified tradeoff-based approach ⋮ Towards optimal kernel for edge-disjoint triangle packing ⋮ 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 ⋮ Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials ⋮ Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs ⋮ Unnamed Item ⋮ 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 ⋮ Algorithms for maximum internal spanning tree problem for some graph classes ⋮ Better approximation algorithms for the maximum internal spanning tree problem

This page was built for publication: A linear vertex kernel for maximum internal spanning tree