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
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references