Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs (Q1183585)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs |
scientific article |
Statements
Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs (English)
0 references
28 June 1992
0 references
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.
0 references
polynomial time algorithm
0 references
EREW PRAM
0 references
parallel algorithm
0 references
dominating clique
0 references
permutation graph
0 references
0 references