论文标题
最小罗马主导功能：扩展和枚举
Minimal Roman Dominating Functions: Extensions and Enumeration
论文作者
论文摘要
罗马统治是统治的众多变体之一，它使经典统治问题的大多数复杂性特征保持不变。我们证明罗马统治在两个方面的行为不同：枚举和扩展。我们开发了具有多项式延迟和多项式空间的最小罗马统治函数的非平凡枚举算法。回想一下，几十年来，最低限度的主导集的存在类似的枚举结果是开放的。我们的结果是基于用于扩展罗马统治的多项式时间算法：给定图形$ g =（v，e）$和一个函数$ f：v \ to \ {0,1,1,2 \} $，是否有最少的罗马统治函数$ \ tilde $ \ tilde {f} $ f \ f \ leq leq f \ leq \ tilde f}在这里，$ \ leq $ lifts $ 0 <1 <2 $ pointSise;以此顺序可以理解最小性。还从输入敏感的角度分析了我们的枚举算法，从而导致$ \ oh（\ romanupperbound^n）$的运行时间估计值n订单n；这是由$ω（\ romanlower -bound^n）$的下限示例进行补充。
Roman domination is one of the many variants of domination that keeps most of the complexity features of the classical domination problem. We prove that Roman domination behaves differently in two aspects: enumeration and extension. We develop non-trivial enumeration algorithms for minimal Roman domination functions with polynomial delay and polynomial space. Recall that the existence of a similar enumeration result for minimal dominating sets is open for decades. Our result is based on a polynomial-time algorithm for Extension Roman Domination: Given a graph $G = (V,E)$ and a function $f:V\to\{0,1,2\}$, is there a minimal Roman domination function $\Tilde{f}$ with $f\leq \Tilde{f}$? Here, $\leq$ lifts $0< 1< 2$ pointwise; minimality is understood in this order. Our enumeration algorithm is also analyzed from an input-sensitive viewpoint, leading to a run-time estimate of $\Oh(\RomanUpperbound^n)$ for graphs of order n; this is complemented by a lower bound example of $Ω(\RomanLowerbound^n)$.
