Anzeige
Erschienen in:
11.11.2020 | Original Research
An \(O(n+m)\) time algorithm for computing a minimum semitotal dominating set in an interval graph
Erschienen in: Journal of Applied Mathematics and Computing | Ausgabe 1-2/2021
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Let \(G=(V,E)\) be a graph without isolated vertices. A set \(D\subseteq V\) is said to be a dominating set of G if for every vertex \(v\in V\setminus D\), there exists a vertex \(u\in D\) such that \(uv\in E\). A set \(D\subseteq V\) is called a semitotal dominating set of G if D is a dominating set and every vertex in D is within distance 2 from another vertex of D. For a given graph G, the semitotal domination problem is to find a semitotal dominating set of G with minimum cardinality. The decision version of the semitotal domination problem is shown to be NP-complete for chordal graphs and bipartite graphs. Henning and Pandey (Theor Comput Sci 766:46–57, 2019) proposed an \(O(n^2)\) time algorithm for computing a minimum semitotal dominating set in interval graphs. In this paper, we show that for a given interval graph \(G=(V,E)\), a minimum semitotal dominating set of G can be computed in \(O(n+m)\) time, where \(n=|V|\) and \(m=|E|\). This improves the complexity of the semitotal domination problem for interval graphs from \(O(n^2)\) to \(O(n+m)\).