Hitting forbidden minors: approximation and kernelization
type: Item
instance of: scholarly article
zbMATH Open document ID: 1336.68123
DOI: 10.1137/140997889
author: Fedor V. Fomin
author: Daniel Lokshtanov
author: Neeldhara Misra
author: Geevarghese Philip
author: Saket Saurabh
published in: SIAM Journal on Discrete Mathematics
publication date: 2016-03-04T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2011/3010/
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C83
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6549695
zbMATH Keywords: kernelization
zbMATH Keywords: minor
zbMATH Keywords: monadic second-order logic
Wikidata QID: Q60488375
MaRDI profile type: Publication
OpenAlex ID: W1787689584
cites work: Crown structures for vertex cover kernelization
cites work: Q3579375
cites work: On the solution of linear recurrence equations
cites work: Q5417644
cites work: An algebraic theory of graph reduction
cites work: Easy problems for tree-decomposable graphs
cites work: A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
cites work: A linear-time approximation algorithm for the weighted vertex cover problem
cites work: Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: A Cubic Kernel for Feedback Vertex Set
cites work: Kernelization: New Upper and Lower Bound Techniques
cites work: On problems without polynomial kernels
cites work: (Meta) Kernelization
cites work: Parallel Algorithms with Optimal Speedup for Bounded Treewidth
cites work: Kernel Bounds for Disjoint Cycles and Disjoint Paths
cites work: Reduction algorithms for graphs of small treewidth
cites work: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
cites work: The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
cites work: Polynomial bounds for the grid-minor theorem
cites work: Vertex cover: Further observations and further improvements
cites work: Graph-Theoretic Concepts in Computer Science
cites work: A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
cites work: Excluded Grid Theorem
cites work: Unit disk graphs
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Q4353558
cites work: Monadic second-order evaluations on tree-decomposable graphs
cites work: Parameterized Algorithms
cites work: An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion
cites work: Q4255109
cites work: Parameterized and Exact Computation
cites work: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
cites work: Q4393480
cites work: On Independent Circuits Contained in a Graph
cites work: Improved Approximation Algorithms for Minimum Weight Vertex Separators
cites work: Nonconstructive tools for proving polynomial-time decidability
cites work: Hitting Diamonds and Growing Cacti
cites work: Parametrized complexity theory.
cites work: Bidimensionality and Geometric Graphs
cites work: Q3549693
cites work: Uniform Kernelization Complexity of Hitting Forbidden Minors
cites work: Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
cites work: Reducibility among Combinatorial Problems
cites work: Treewidth. Computations and approximations
cites work: Approximation properties of NP minimization classes
cites work: Polynomial Kernelizations For MIN F+Pi1 And MAX NP
cites work: The node-deletion problem for hereditary properties is NP-complete
cites work: The approximation of maximum subgraph problems
cites work: Properties of vertex packing and independence system polyhedra
cites work: Q5710169
cites work: Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
cites work: Looking at the stars
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Quickly excluding a planar graph
cites work: A 4 k 2 kernel for feedback vertex set

Hitting forbidden minors: approximation and kernelization (DBLP publication ID)
DBLP publication ID: journals/siamdm/FominLMPS16

Hitting forbidden minors: approximation and kernelization (title)
title: Hitting forbidden minors: approximation and kernelization