Linear kernels for (connected) dominating set on H-minor-free graphs
From MaRDI portal
Publication:5743379
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
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 7051285 (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?)
- (Meta) Kernelization
- A Separator Theorem for Nonplanar Graphs
- A partial k-arboretum of graphs with bounded treewidth
- A simpler algorithm and shorter proof for the graph minor decomposition
- 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
- 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
(23)- Designing FPT algorithms for cut problems using randomized contractions
- scientific article; zbMATH DE number 7204413 (Why is no real title available?)
- Lossy kernels for connected dominating set on sparse graphs
- The effect of girth on the kernelization complexity of connected dominating set
- scientific article; zbMATH DE number 7764102 (Why is no real title available?)
- Characterising bounded expansion by neighbourhood complexity
- Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
- Linear Kernel for Planar Connected Dominating Set
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
- Lossy kernels for connected dominating set on sparse graphs
- Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs
- Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
- Domination above \(r\)-independence: does sparseness help?
- Algorithmic properties of sparse digraphs
- Explicit linear kernels via dynamic programming
- Combing a Linkage in an Annulus
- Nonblocker in \(H\)-minor free graphs: kernelization meets discharging
- Circumventing connectivity for kernelization
- Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
- Computing paths of large rank in planar frameworks deterministically
- Editing to a planar graph of given degrees
- Editing to a planar graph of given degrees
- Kernels for (connected) dominating set on graphs with excluded topological minors
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)
