Weighted domination of cocomparability graphs (Q1382270)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1133166
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Weighted domination of cocomparability graphs |
scientific article; zbMATH DE number 1133166 |
Statements
Weighted domination of cocomparability graphs (English)
0 references
25 March 1998
0 references
The paper investigates weighted domination (in some variants) for the class of cocomparability graphs and the subclass of cobipartite graphs. It is shown that these problems are NP-complete for the class of cobipartite graphs when arbitrary integers as weights are allowed while all these problems can be solved in polynomial time for the larger class of cocomparability graphs if the vertex weights are integers bounded by some constant. In particular an \(O(n^2)\)-algorithm is given for the weighted independent perfect domination problem on cocomparability graphs of order \(n\).
0 references
weighted domination
0 references
cocomparability graphs
0 references
cobipartite graphs
0 references
NP-complete
0 references
0 references
0.965623676776886
0 references
0.8466194868087769
0 references
0.8429545164108276
0 references
