论文标题
罗马人口普查：列举和计算罗马在图类上的主导功能
Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes
论文作者
论文摘要
最近已经研究了有关列举和计数的罗马统治概念（WG 2022）。已经表明，最小的罗马统治功能可以用多项式延迟来列举，与最小的主导集所知的对比。该算法的运行时间可以估计为$ n $的一般图上的$ \ Mathcal {O}（1.9332^n）$。在本文中，我们专注于特殊的图表类。更具体地说，对于和弦图，我们提出了一种枚举算法$ \ MATHCAL {O}（1.8940^n）$。对于间隔图，我们可以将这时间降低到$ \ MATHCAL {O}（1.7321^n）$。有趣的是，这也与已知的下限（完全）匹配。我们还可以为森林提供匹配的下层和上限，这是（顺便说一句），即$ \ Mathcal {o}（\ sqrt {3}^n）$。此外，我们显示了一种随时间运行的枚举算法$ \ MATHCAL {O}（1.4656^n）$用于拆分图和Cobipartite图。我们的方法还允许提供具体的公式，以计算在路径（如路径）上的最小罗马统治功能。
The concept of Roman domination has recently been studied concerning enumerating and counting (WG 2022). It has been shown that minimal Roman dominating functions can be enumerated with polynomial delay, contrasting what is known about minimal dominating sets. The running time of the algorithm could be estimated as $\mathcal{O}(1.9332^n)$ on general graphs of order $n$. In this paper, we focus on special graph classes. More specifically, for chordal graphs, we present an enumeration algorithm running in time $\mathcal{O}(1.8940^n)$. For interval graphs, we can lower this time further to $\mathcal{O}(1.7321^n)$. Interestingly, this also matches (exactly) the known lower bound. We can also provide a matching lower and upper bound for forests, which is (incidentally) the same, namely $\mathcal{O}(\sqrt{3}^n)$. Furthermore, we show an enumeration algorithm running in time $\mathcal{O}(1.4656^n)$ for split graphs and for cobipartite graphs. Our approach also allows to give concrete formulas for counting minimal Roman dominating functions on special graph families like paths.
