Domination above r-independence: does sparseness help?

DOI10.4230/LIPICS.MFCS.2019.40MaRDI QIDQ5092402zbMATH OpenFDO

Authors Carl Einarson, Felix Reidl

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1906.09180

zbMATH Keywords

kerneldominating setnowhere densebounded expansionabove guarantee

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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

• scientific article; zbMATH DE number 6678911 (Why is no real title available?)
• A simplified NP-complete satisfiability problem
• All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables
• Betweenness parameterized above tight lower bound
• Bidimensionality and kernels
• Faster parameterized algorithms using linear programming
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Kernelization and Sparseness: the case of Dominating Set
• Kernelization using structural parameters on sparse graph classes
• Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Neighborhood complexity and kernelization for nowhere dense classes of graphs
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Parameterizing above or below guaranteed values
• Planar Formulae and Their Uses
• Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
• Polynomial-time data reduction for dominating set
• Solving MAX-\(r\)-SAT above a tight lower bound
• Sparsity. Graphs, structures, and algorithms
• Testing first-order properties for subclasses of sparse graphs
• The linear arrangement problem parameterized above guaranteed value
• Vertex cover problem parameterized above and below tight bounds

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)