An $$O(n+m)$$ O ( n + m ) time algorithm for computing a minimum semitotal dominating set in an interval graph
- PDF / 400,998 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 20 Downloads / 188 Views
An O(n + m) time algorithm for computing a minimum semitotal dominating set in an interval graph D. Pradhan1 · Saikat Pal1 Received: 12 September 2020 / Revised: 28 October 2020 / Accepted: 30 October 2020 © Korean Society for Informatics and Computational Applied Mathematics 2020
Abstract Let G = (V , E) be a graph without isolated vertices. A set D ⊆ V is said to be a dominating set of G if for every vertex v ∈ V \ D, there exists a vertex u ∈ D such that uv ∈ E. A set D ⊆ 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). Keywords Domination · Total domination · Semitotal domination · Interval graphs · Polynomial time algorithm Mathematics Subject Classification 05C69 · 68Q25
1 Introduction Let G = (V , E) be a graph without isolated vertices. The sets N G (v) = {u ∈ V : uv ∈ E} and N G [v] = N G (v) ∪ {v} denote the neighborhood and the closed neighborhood of a vertex v, respectively. The degree of a vertex v is |N G (v)| and is denoted by dG (v).
B
Saikat Pal [email protected] D. Pradhan [email protected]
1
Department of Mathematics and Computing, Indian Institute of Technology (ISM), Dhanbad, India
123
D. Pradhan, S. Pal
The distance dG (u, v) between two vertices u and v is the length of the shortest u, vpath in a connected graph G. For a vertex v, the 2-distance neighborhood of v is N G2 (v) = {u : 0 < dG (u, v) ≤ 2}. The closed 2-distance neighborhood of v is N G2 [v] = N G2 (v) ∪ {v}. A set D ⊆ V of a graph G = (V , E) is called a dominating set of G if every vertex in V \ D is adjacent to a vertex in D. The cardinality of a smallest dominating set of G, denoted by γ (G) is called the domination number of G. The concept of domination and its variations have been widely studied in theoretical, algorithmic and application aspects (see [4,5]). A set D ⊆ V of a graph G = (V , E) is a called total dominating set of G if every vertex in V is adjacent to some vertex in D. The total domination number of G, denoted by γt (G), is the minimum cardinality of a total dominating set of G. An excellent survey of total domination in graphs can be found in [6]. Some selected results have also been described by Henning and Yeo in [12]. A new variant of total domination, namely semitotal domination has been introduced by Goddard et al. [3] and studied
Data Loading...
