Linear kernels for (connected) dominating set on H-minor-free graphs
From MaRDI portal
(Redirected from Publication:5743379)
Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
Recommendations
- Kernels for (connected) dominating set on graphs with excluded topological minors
- Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
- Linear Kernel for Planar Connected Dominating Set
- A linear kernel for a planar connected dominating set
- Bidimensionality and kernels
Cites work
- (Meta) Kernelization
- A partial k-arboretum of graphs with bounded treewidth
- A Separator Theorem for Nonplanar Graphs
- A simpler algorithm and shorter proof for the graph minor decomposition
- Algorithms for finding an induced cycle in planar graphs and bounded genus graphs
- Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- Bidimensionality and kernels
- Bidimensionality: new connections between FPT algorithms and PTASs
- Contraction obstructions for treewidth
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Domination problems in nowhere-dense classes of graphs
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Fourier meets M\"{o}bius: fast subset convolution
- Fundamentals of parameterized complexity
- Grad and classes with bounded expansion. II: Algorithmic aspects
- Graph minors. XIII: The disjoint paths problem
- Graph minors. XVI: Excluding a non-planar graph
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- scientific article; zbMATH DE number 6783430 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
- Linearity of grid minors in treewidth with applications through bidimensionality
- Local tree-width, excluded minors, and approximation algorithms
- Odd cycle packing
- On problems without polynomial kernels
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Parametrized complexity theory.
- Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
- Polynomial-time data reduction for dominating set
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
- Spanners in Sparse Graphs
- Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
- The Induced Disjoint Paths Problem
- Tight bounds for linkages in planar graphs
Cited in
(29)- Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
- Characterising bounded expansion by neighbourhood complexity
- Kernelization and approximation of distance-r independent sets on nowhere dense graphs
- Circumventing connectivity for kernelization
- The effect of girth on the kernelization complexity of connected dominating set
- Explicit linear kernels via dynamic programming
- Designing FPT algorithms for cut problems using randomized contractions
- Editing to a planar graph of given degrees
- Lossy kernels for connected dominating set on sparse graphs
- Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
- Linear Kernel for Planar Connected Dominating Set
- Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
- Kernels for (connected) dominating set on graphs with excluded topological minors
- Nonblocker in H-minor free graphs: kernelization meets discharging
- Algorithmic properties of sparse digraphs
- Domination above \(r\)-independence: does sparseness help?
- scientific article; zbMATH DE number 7204413 (Why is no real title available?)
- Lossy kernels for connected dominating set on sparse graphs
- Combing a Linkage in an Annulus
- scientific article; zbMATH DE number 7764102 (Why is no real title available?)
- Computing paths of large rank in planar frameworks deterministically
- Sidestepping barriers for dominating set in parameterized complexity
- Sunflowers meet sparsity: a linear-vertex kernel for weighted clique-packing on sparse graphs
- Computing paths of large rank in planar frameworks deterministically
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- Fine-grained complexity of multiple domination and dominating patterns in sparse graphs
- Editing to a planar graph of given degrees
This page was built for publication: Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743379)
