Connected domination and dominating clique in trapezoid graphs (Q1962037)

From MaRDI portal
Revision as of 16:36, 1 February 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
scientific article
Language Label Description Also known as
English
Connected domination and dominating clique in trapezoid graphs
scientific article

    Statements

    Connected domination and dominating clique in trapezoid graphs (English)
    0 references
    0 references
    24 September 2000
    0 references
    The class of trapezoid graphs is defined as the intersection graphs of a collection of trapezoids. A set of vertices that dominates the graph and induces a connected graph is a connected dominating set. The smallest set is called the connected domination number for the graph. It is known that this problem is NP-hard. The author develops an \(O(n)\) algorithm for finding a minimum connected dominating set in a trapezoid graph. If a trapezoid graph has a dominating clique, the author develops an \(O(m+n)\) algorithm for finding such a clique. This algorithm depends on the fact that if such a clique exists, then it has cardinality at most four.
    0 references
    trapezoid graphs
    0 references
    connected dominating set
    0 references
    connected domination number
    0 references
    algorithm
    0 references
    dominating clique
    0 references

    Identifiers