A linear-time algorithm for semitotal domination in strongly chordal graphs (Q6110593)
From MaRDI portal
scientific article; zbMATH DE number 7721330
Language | Label | Description | Also known as |
---|---|---|---|
English | A linear-time algorithm for semitotal domination in strongly chordal graphs |
scientific article; zbMATH DE number 7721330 |
Statements
A linear-time algorithm for semitotal domination in strongly chordal graphs (English)
0 references
2 August 2023
0 references
A set \(D\) of vertices in an isolate-free graph \(G\) is a semitotal dominating set of \(G\) if \(D\) is a dominating set of \(G\) and every vertex in \(D\) is within distance two from another vertex of \(D\). The semitotal domination number of \(G\) is the minimum cardinality of a semitotal dominating set of \(G\) and is denoted by \(\gamma_{t2}(G)\). The Minimum Semitotal Domination problem is to find a minimum cardinality semitotal dominating set of \(G\). It is known that the decision version of the problem remains NP-complete even when restricted to chordal graphs, chordal bipartite graphs, and planar graphs. The authors in this paper, resolve the complexity of the problem in strongly chordal graphs by designing a linear-time algorithm for the problem.
0 references
total domination
0 references
semitotal domination
0 references
strongly chordal graphs
0 references
polynomial-time algorithm
0 references
0 references
0 references
0 references