ﻻ يوجد ملخص باللغة العربية
Dealing with the NP-complete Dominating Set problem on undirected graphs, we demonstrate the power of data reduction by preprocessing from a theoretical as well as a practical side. In particular, we prove that Dominating Set restricted to planar graphs has a so-called problem kernel of linear size, achieved by two simple and easy to implement reduction rules. Moreover, having implemented our reduction rules, first experiments indicate the impressive practical potential of these rules. Thus, this work seems to open up a new and prospective way how to cope with one of the most important problems in graph theory and combinatorial optimization.
Dealing with NP-hard problems, kernelization is a fundamental notion for polynomial-time data reduction with performance guarantees: in polynomial time, a problem instance is reduced to an equivalent instance with size upper-bounded by a function of
This paper is devoted to the online dominating set problem and its variants. We believe the paper represents the first systematic study of the effect of two limitations of online algorithms: making irrevocable decisions while not knowing the future,
We show that the k-Dominating Set problem is fixed parameter tractable (FPT) and has a polynomial kernel for any class of graphs that exclude K_{i,j} as a subgraph, for any fixed i, j >= 1. This strictly includes every class of graphs for which this
Given a graph $G=(V,E)$ and an integer $k ge 1$, a $k$-hop dominating set $D$ of $G$ is a subset of $V$, such that, for every vertex $v in V$, there exists a node $u in D$ whose hop-distance from $v$ is at most $k$. A $k$-hop dominating set of minimu
We recently introduced the graph invariant twin-width, and showed that first-order model checking can be solved in time $f(d,k)n$ for $n$-vertex graphs given with a witness that the twin-width is at most $d$, called $d$-contraction sequence or $d$-se