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

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

Mathematics Subject Classification ID

68R10

0 references

0 references

0 references

0 references

NP-completeness

0 references

chordal bipartite graphs

0 references

Steiner tree

0 references

dominating set

0 references

reviewed by

Giora Slutzki

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/0304-3975(87)90067-3

0 references

0 references

0 references

On domination problems for permutation and other graphs

0 references

Domination in permutation graphs

0 references

Q4198056

0 references

Q3328583

0 references

The NP-completeness column: an ongoing guide

0 references

Reducibility among Combinatorial Problems

0 references

Bipartite permutation graphs

0 references

Steiner trees, connected domination and strongly chordal graphs

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1099628

@@ Property / reviewed by @@
+Giora Slutzki
@@ Property / reviewed by: Giora Slutzki / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0304-3975(87)90067-3
+Normal rank
@@ Property / OpenAlex ID @@
+W2058460385
@@ Property / OpenAlex ID: W2058460385 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3694712
@@ Property / cites work: Q3694712 / rank @@
+Normal rank
@@ Property / cites work @@
+On domination problems for permutation and other graphs
+Normal rank
@@ Property / cites work @@
+Domination in permutation graphs
@@ Property / cites work: Domination in permutation graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3328583
@@ Property / cites work: Q3328583 / rank @@
+Normal rank
@@ Property / cites work @@
+The NP-completeness column: an ongoing guide
@@ Property / cites work: The NP-completeness column: an ongoing guide / rank @@
+Normal rank
@@ Property / cites work @@
+Reducibility among Combinatorial Problems
@@ Property / cites work: Reducibility among Combinatorial Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Bipartite permutation graphs
@@ Property / cites work: Bipartite permutation graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Steiner trees, connected domination and strongly chordal graphs
+Normal rank