Fine-grained complexity of multiple domination and dominating patterns in sparse graphs

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Cites work

scientific article; zbMATH DE number 3910446 (Why is no real title available?)
scientific article; zbMATH DE number 3914370 (Why is no real title available?)
scientific article; zbMATH DE number 3914371 (Why is no real title available?)
scientific article; zbMATH DE number 2079336 (Why is no real title available?)
scientific article; zbMATH DE number 1792607 (Why is no real title available?)
scientific article; zbMATH DE number 1414320 (Why is no real title available?)
A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
A generalised upper bound for the k-tuple domination number
A new algorithm for optimal 2-constraint satisfaction and its implications
A note on \(r\)-dominating cliques
A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs
A tight bound for independent domination of cubic graphs without 4‐cycles
Circumference of a graph and its distance dominating longest cycles
Complexity of \(k\)-tuple total and total \(\{k\}\)-dominations for some subclasses of bipartite graphs
Connected k-tuple twin domination in de Bruijn and Kautz digraphs
Connected domination and dominating clique in trapezoid graphs
Counting dominating sets and related structures in graphs
Degree sum and vertex dominating paths
Distributed maximal matching and maximal independent set on hypergraphs
Dominating cliques in chordal graphs
Dominating cliques in graphs
Dynamic \(((1+\epsilon)\ln n)\)-approximation algorithms for minimum set cover and dominating set
Existence of dominating cycles and paths
Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
Fixed-Parameter Tractability and Completeness I: Basic Results
Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
Fully dynamic maximal independent set with sublinear update time
If the current clique algorithms are optimal, so is Valiant's parser
Independent domination of graphs with bounded maximum degree
Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
Local computation of maximal independent set
Minimum degree and dominating paths
New bounds for matrix multiplication: from alpha to omega
Nordhaus-Gaddum inequalities for domination in graphs
On dominating set polyhedra of circular interval graphs
On independent domination in direct products
On independent domination of regular graphs
On some fine-grained questions in algorithms and complexity
On the complexity of \(\{k\}\)-domination and \(k\)-tuple domination in graphs
On the complexity of fixed parameter clique and dominating set
On the dominating (induced) cycles of iterated line graphs
On the maximum number of minimum dominating sets in forests
On the parameterized complexity of approximating dominating set
On the possibility of faster \textsc{SAT} algorithms
Quadratic conditional lower bounds for string problems and dynamic time warping
Reconfiguration of dominating sets
Rounds vs communication tradeoffs for maximal independent sets
The \(k\)-tuple twin domination in de Bruijn and Kautz digraphs
The effect of sparsity on k-Dominating Set and related first-order graph properties
Tight hardness for shortest cycles and paths in sparse graphs
Trees with extremal numbers of \(k\)-dominating sets
k-tuple total domination in graphs

This page was built for publication: Fine-grained complexity of multiple domination and dominating patterns in sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7255445)