The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
type: Item
instance of: scholarly article
title: The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
zbMATH Open document ID: 0638.68062
DOI: 10.1016/0304-3975(87)90067-3
author: Haiko Müller
author: Andreas Brandstädt
published in: Theoretical Computer Science
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 4041288
zbMATH Keywords: NP-completeness
zbMATH Keywords: chordal bipartite graphs
zbMATH Keywords: Steiner tree
zbMATH Keywords: dominating set
reviewed by: Giora Slutzki
MaRDI profile type: Publication
full work available at URL: 0304-3975(87)90067-3
OpenAlex ID: W2058460385
cites work: Q3694712
cites work: On domination problems for permutation and other graphs
cites work: Domination in permutation graphs
cites work: Q4198056
cites work: Q3328583
cites work: The NP-completeness column: an ongoing guide
cites work: Reducibility among Combinatorial Problems
cites work: Bipartite permutation graphs
cites work: Steiner trees, connected domination and strongly chordal graphs
description: scientific article; zbMATH DE number 4041288