The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs (Q1099628)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
scientific article

    Statements

    The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs (English)
    0 references
    0 references
    0 references
    1987
    0 references
    The authors show that several known NP-complete problems (for general graphs) remain NP-complete even when restricted to chordal bipartite graphs. The problems in question are Steiner tree, dominating set and connected dominating set.
    0 references
    NP-completeness
    0 references
    chordal bipartite graphs
    0 references
    Steiner tree
    0 references
    dominating set
    0 references
    0 references

    Identifiers