The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
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.
scientific article; zbMATH DE number 4041288
scientific article