Computing Roman domatic number of graphs

Haisheng Tan,Hongyu Liang,Rui Wang,Jipeng Zhou

Information Processing Letters（2016）

引用 4|浏览38

暂无评分

摘要

•We show that it is NP-complete to decide whether the Roman domatic number of a given graph is at least three.•We then prove an asymptotically optimal threshold of Θ(log⁡n) for approximating the Roman domatic number of a graph.•Finally, we also determine the exact values of the Roman domatic number in some particular classes of graphs.

查看译文

关键词

Roman domatic number,Graph,Computational complexity,Approximation algorithms

AI 理解论文

溯源树

样例

生成溯源树，研究论文发展脉络

Chat Paper

正在生成论文摘要