An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs (Q1566569): Difference between revisions

A vertex set \(S\) is said to be a dominating set for an undirected graph \((V,E)\) if for every vertex \(i\) in \(V\setminus S\) there is a vertex \(j\) in \(S\) such that \((i,j)\) belongs to \(E,A\) permutation graph is an undirected graph constructed on a given permutation of the numbers \(1, \dots,n\). The paper deals with a minimum cardinality dominating set problem: for given a permutation graph find the dominating set \(S\) with the minimum number of vertices. The authors present the linear time algorithm for the problem which is based on dynamic programming approach. The paper, which is not easy to read, brings new result. The best previous \(O(n\log\log n)\) algorithm is described by \textit{K. H. Tsai} and \textit{W. L. Hsu} in [Algorithmica 9, 601--614 (1993; Zbl 0768.68063)].