Linear kernels for (connected) dominating set on H-minor-free graphs
From MaRDI portal
Publication:5743379
zbMATH Open1421.68078MaRDI QIDQ5743379FDOQ5743379
Authors: Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos 
Publication date: 10 May 2019
Full work available at URL: https://dl.acm.org/citation.cfm?id=2095123
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
Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph minors (05C83)
Cites Work
- Fundamentals of parameterized complexity
- Title not available (Why is that?)
- On problems without polynomial kernels
- A partial k-arboretum of graphs with bounded treewidth
- Graph minors. XIII: The disjoint paths problem
- Grad and classes with bounded expansion. II: Algorithmic aspects
- Parametrized complexity theory.
- Title not available (Why is that?)
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Title not available (Why is that?)
- Odd cycle packing
- A Separator Theorem for Nonplanar Graphs
- (Meta) Kernelization
- Bidimensionality and kernels
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Polynomial-time data reduction for dominating set
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Domination problems in nowhere-dense classes of graphs
- Bidimensionality: new connections between FPT algorithms and PTASs
- Fourier meets M\"{o}bius: fast subset convolution
- Title not available (Why is that?)
- Tight bounds for linkages in planar graphs
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Graph minors. XVI: Excluding a non-planar graph
- Local tree-width, excluded minors, and approximation algorithms
- The Induced Disjoint Paths Problem
- Title not available (Why is that?)
- Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
- Contraction obstructions for treewidth
- Linearity of grid minors in treewidth with applications through bidimensionality
- Spanners in Sparse Graphs
- A simpler algorithm and shorter proof for the graph minor decomposition
- Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
- Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
Cited In (23)
- Designing FPT algorithms for cut problems using randomized contractions
- Title not available (Why is that?)
- Lossy kernels for connected dominating set on sparse graphs
- The effect of girth on the kernelization complexity of connected dominating set
- Title not available (Why is that?)
- Characterising bounded expansion by neighbourhood complexity
- Linear Kernel for Planar Connected Dominating Set
- Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
- Lossy kernels for connected dominating set on sparse graphs
- Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
- Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs
- 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
- Computing paths of large rank in planar frameworks deterministically
- Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
- 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)
