论文标题
计数有向路径图中的主导集
Counting Dominating Sets in Directed Path Graphs
论文作者
论文摘要
一组统治图是一组顶点，使得集合中的每个顶点在集合中至少有一个邻居。计数主导集的问题是弦图的＃P-Complete，但可以在多项式时间内解决其间隔图的子类。对于有向路径图的相应问题的复杂性状态仍未确定，这是众所周知的一类图形，属于弦图和间隔图之间。本文表明，计数统治集的问题仍然是有向路径图的＃p组，但是对根的有向路径图的更严格的约束允许多项式时间解决方案。
A dominating set of a graph is a set of vertices such that every vertex not in the set has at least one neighbor in the set. The problem of counting dominating sets is #P-complete for chordal graphs but solvable in polynomial time for its subclass of interval graphs. The complexity status of the corresponding problem is still undetermined for directed path graphs, which are a well-known class of graphs that falls between chordal graphs and interval graphs. This paper reveals that the problem of counting dominating sets remains #P-complete for directed path graphs but a stricter constraint to rooted directed path graphs admits a polynomial-time solution.
