二部置换图的无圈控制集算法

Algorithm of Acyclic Dominating Set Problem on Bipartite Permutation Graphs

设G=(V,E)为简单无向图,S V称为G的无圈控制集,如果S控制G并且导出子图〈S〉不含有圈.该文证明了二部置换图的无圈控制数等于其控制数(γa(G)=γ(G)),利用此结论证明了无圈控制集问题在二部置换图上具有线性时间求解算法.

Let G = （ V, E） be a simple undirected graph, a subset S （真包含于） V is called an acyclic dominating set of G if S dominates G and the induced subgraph （S） contains no cycles. This paper shows that the acyclic domination number of a bipartite permutation graph is equal to its domination number, i.e.,γa （ G ） =γ（G）. With this result it is shown that a linear time algorithm can be obtained to compute a minimumcardinality acyclic dominating set on bipartite pernutation graphs.