Twin-width and polynomial kernels
type: Item
instance of: scholarly article
title: Twin-width and polynomial kernels
author: Édouard Bonnet
author: Eun Jung Kim
author: Amadeus Reinald
author: Rémi Watrigant
author: Stéphan Thomassé
published in: Algorithmica
publication date: 2022-10-27T00:00:00Z
full work available at URL: https://arxiv.org/abs/2107.02882
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7608292
zbMATH Keywords: twin-width
zbMATH Keywords: kernelization
zbMATH Keywords: lower bounds
zbMATH Keywords: dominating set
MaRDI profile type: Publication
OpenAlex ID: W3181611173
cites work: Polynomial-time data reduction for dominating set
cites work: Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
cites work: On problems without polynomial kernels
cites work: Twin-width I: Tractable FO Model Checking
cites work: Parameterized domination in circle graphs
cites work: Q5743501
cites work: Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
cites work: Strong computational lower bounds via parameterized complexity
cites work: Unit disk graphs
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Deterministic Parameterized Connected Vertex Cover
cites work: Parameterized Algorithms
cites work: Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
cites work: Dominating set is fixed parameter tractable in claw-free graphs
cites work: Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
cites work: Domination problems in nowhere-dense classes of graphs
cites work: Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
cites work: Kernelization Lower Bounds Through Colors and IDs
cites work: Dynamic Programming and Fast Matrix Multiplication
cites work: Fundamentals of parameterized complexity
cites work: Kernelization and Sparseness: the case of Dominating Set
cites work: Domination in permutation graphs
cites work: Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors
cites work: Bidimensionality and Kernels
cites work: Automata, Languages and Programming
cites work: Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
cites work: Kernelization using structural parameters on sparse graph classes
cites work: Some simplified NP-complete graph problems
cites work: Parameterized Complexity for Domination Problems on Degenerate Graphs
cites work: Deciding First-Order Properties of Nowhere Dense Graphs
cites work: Corrigendum to our paper ''The ellipsoid method and its consequences in combinatorial optimization''
cites work: Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor
cites work: A simple linear time algorithm for cograph recognition
cites work: Domination When the Stars Are Out
cites work: Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
cites work: Exploiting c-Closure in Kernelization Algorithms for Graph Problems
cites work: Planar Formulae and Their Uses
cites work: Excluded permutation matrices and the Stanley-Wilf conjecture
cites work: Sparsity. Graphs, structures, and algorithms
cites work: Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond
cites work: Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
cites work: FPT algorithms for domination in sparse graphs and beyond
DOI: 10.1007/S00453-022-00965-5
description: scientific article; zbMATH DE number 7608292