Domination above r-independence: does sparseness help?
From MaRDI portal
Publication:5092402
DOI10.4230/LIPICS.MFCS.2019.40MaRDI QIDQ5092402FDOQ5092402
Authors: Carl Einarson, Felix Reidl 
Publication date: 21 July 2022
Full work available at URL: https://arxiv.org/abs/1906.09180
Recommendations
- Kernelization and Sparseness: the case of Dominating Set
- On distance \(r\)-dominating and \(2r\)-independent sets in sparse graphs
- FPT algorithms for domination in sparse graphs and beyond
- Domination problems in nowhere-dense classes of graphs
- On the Parameterized Complexity of [1,j]-Domination Problems
Cites Work
- Parameterizing above or below guaranteed values
- Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
- Betweenness parameterized above tight lower bound
- Planar Formulae and Their Uses
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Solving MAX-\(r\)-SAT above a tight lower bound
- A simplified NP-complete satisfiability problem
- Bidimensionality and kernels
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- The linear arrangement problem parameterized above guaranteed value
- Sparsity. Graphs, structures, and algorithms
- Kernelization using structural parameters on sparse graph classes
- Polynomial-time data reduction for dominating set
- Kernelization and Sparseness: the case of Dominating Set
- Faster parameterized algorithms using linear programming
- Vertex cover problem parameterized above and below tight bounds
- All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables
- Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
- Title not available (Why is that?)
- Testing first-order properties for subclasses of sparse graphs
- Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
- Neighborhood complexity and kernelization for nowhere dense classes of graphs
This page was built for publication: Domination above \(r\)-independence: does sparseness help?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5092402)
