Kernelization and Sparseness: the case of Dominating Set
From MaRDI portal
Publication:4601883
DOI10.4230/LIPIcs.STACS.2016.31zbMath1388.68110arXiv1411.4575OpenAlexW2963587624MaRDI QIDQ4601883
No author found.
Publication date: 24 January 2018
Full work available at URL: https://arxiv.org/abs/1411.4575
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Improved bounds for weak coloring numbers, Characterising bounded expansion by neighbourhood complexity, Decremental Optimization of Dominating Sets Under the Reconfiguration Framework, On the Parameterized Complexity of the Expected Coverage Problem, On the parameterized complexity of reconfiguration of connected dominating sets, On the parameterized complexity of the expected coverage problem, Kernelization using structural parameters on sparse graph classes, Reconfiguration on nowhere dense graph classes, Harmless sets in sparse classes, Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs, Linear kernels for outbranching problems in sparse digraphs, Sublinear separators, fragility and subexponential expansion, Bounds on half graph orders in powers of sparse graphs, Unnamed Item, Unnamed Item, On directed covering and domination problems, Reconfiguration on sparse graphs, On the generalised colouring numbers of graphs that exclude a fixed minor, Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs, Unnamed Item, Unnamed Item, Unnamed Item, Lossy Kernels for Connected Dominating Set on Sparse Graphs, Unnamed Item, Bidimensionality and Kernels, Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness, On approximate preprocessing for domination and hitting subgraphs with connected deletion sets, Lossy Kernels for Connected Dominating Set on Sparse Graphs, Lossy Kernels for Hitting Subgraphs, Twin-width and polynomial kernels, On Directed Covering and Domination Problems, Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness, Constant round distributed domination on graph classes with bounded expansion
