Weighted efficient domination problem on some perfect graphs (Q1348388)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Weighted efficient domination problem on some perfect graphs |
scientific article |
Statements
Weighted efficient domination problem on some perfect graphs (English)
0 references
15 May 2002
0 references
A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called dominating in \(G\), if each vertex of \(G\) either is in \(S\), or is adjacent to a vertex of \(D\). If moreover the distance between arbitrary two vertices of \(D\) is at least 3, then \(D\) is called an efficient dominating set in \(G\). Not in every graph \(G\) an efficient dominating set exists. The paper is devoted to algorithmic problems concerning its existence. In particular, it pays attention to bipartite graphs.
0 references
efficient dominating set
0 references
bipartite graphs
0 references
0 references
0 references
0 references
0 references