Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs (Q1183585)

Given an \(n\)-vertex graph \(G=(V,E)\), a clique of \(G\) that dominates \(V\) is called a dominating clique (DC) of \(G\). Given a permutation graph \(G\) with nonnegative weights on the vertices, the problem addressed in the paper is that of finding any minimum weight DC of \(G\). This problem can be solved in \(O(n^ 2)\) time and \(O(n)\) space or in \(O(n\log n)\) both time and space. An interesting contribution of this paper is that the problem is posed as a special case of a two-dimensional range searching problem. In this way the authors arrive at an \(O(n\log n)\)-time algorithm that uses \(O(n)\) space. They also present an NC parallel version of their algorithm.