A linear algorithm for computing $\gamma_{_{[1,2]}}$-set in generalized series-parallel graphs

Document Type : Research Paper

Authors

Department of Computer Science, Yazd University, Yazd, Iran

Abstract

For a graph $G=(V,E)$, a set $S \subseteq V$ is a $[1,2]$-set if it is a dominating set for $G$ and each vertex $v \in V \setminus S$ is dominated by at most two vertices of $S$, i.e. $1 \leq \vert N(v) \cap S \vert \leq 2$. Moreover a set $S \subseteq V$ is a total $[1,2]$-set if for each vertex of $V$, it is the case that $1 \leq \vert N(v) \cap S \vert \leq 2$. The $[1,2]$-domination number of $G$, denoted $\gamma_{[1,2]}(G)$, is the minimum number of vertices in a $[1,2]$-set. Every $[1,2]$-set with cardinality of $\gamma_{[1,2]}(G)$ is called a $\gamma_{[1,2]}$-set. Total $[1,2]$-domination number and $\gamma_{t[1,2]}$-sets of $G$ are defined in a similar way. This paper presents a linear time algorithm to find a $\gamma_{[1,2]}$-set and a $\gamma_{t[1,2]}$-set in generalized series-parallel graphs.

Keywords

References

[1] A. V. Aho and J. E. Hopcroft, Design & Analysis of Computer Algorithms, Pearson Education India, 1974.
[2] S. C. Chang, J. J. Liu and Y. L. Wang, The weighted independent domination problem in series-parallel graphs,
Intelligent Systems and Applications, 274 (2015) 77–84.
[3] P. Chebolu, M. Cryan and R. Martin, Exact counting of euler tours for generalized series-parallel graphs, J. Discrete
Algorithms, 10 (2012) 110–122.
[4] M. Chellali, T. W. Haynes, S. T. Hedetniemi and A. McRae, [1,2]-sets in graphs, Discrete Appl Math., 161 (2013)
2885–2893.
[5] E. J. Cockayne and S. T. Hedetniemi, Towards a theory of domination in graphs, Networks, 7 (1977) 247–261.
[6] C. J. Colbourn, P. J. Slater and L. K. Stewart, Locating dominating sets in series parallel networks, Congr. Numer,
56 (1987) 135–162.
[7] O. Etesami, N. Ghareghani, M. Habib, M.R. Hooshmandasl, R. Naserasr and P. Sharifani, When an optimal
dominating set with given constraints exists, Theor. Comput. Sci., 780 (2019) 54–65.
[8] M. R. Garey, D. S. Johnson and L. Stockmeyer, Some simplified np-complete graph problems, Theor. Comput. Sci.,
1 (1976) 237–267.
[9] A. Goharshadi and M. R. Hooshmandasl, M. Alambardar Meybodi, [1,2]-sets and [1,2]-total sets in trees with
algorithms, Discrete Appl. Math., 198 (2016) 136–146.
[10] S. Guha and S. Khuller, Approximation algorithms for connected dominating sets, Algorithmica, 20 (1998) 374–387.
[11] S. Guha and S. Khuller, Improved methods for approximating node weighted steiner trees and connected dominating sets, Inform Comput, 150 (1999) 57–74.
[12] E. O. Hare, S. T. Hedetniemi, R. C. Laskar, K. Peters and T. Wimer, Linear-time computability of combinatorial
problems on generalized-series-parallel graphs, Discrete Algorithms and Complexity, (1987) 437–457.
[13] S. T. Hedetniemi, R. Laskar and J. Pfaff, A linear algorithm for finding a minimum dominating set in a cactus,
Discrete Appl Math., 13 (1986) 287–292.
[14] J. E. Hopcroft and R. E. Tarjan, Dividing a graph into triconnected components, SIAM J. Comput., 2 (1973)
135–158.
[15] T. Kikuno, N. Yoshida and Y. Kakuda, A linear algorithm for the domination number of a series-parallel graph.
Discrete Appl. Math., 5 (1983) 299–311.
[16] M. B. Richey and R. G. Parker, Minimum-maximal matching in series-parallel graphs, European J. Oper. Res., 33
(1988) 98–105.
[17] K. Takamizawa, T. Nishizeki and N. Saito, Linear-time computability of combinatorial problems on series-parallel
graphs, J. Assoc. Comput. Mach., 29 (1982) 623–641.
[18] D. B. West, Introduction to graph theory, 2, Prentice hall Upper Saddle River, 2001.
[19] X. Yang and B. Wu, [1,2]-domination in graphs, Discrete Appl. Math., 175 (2014) 79–86.
[20] C.-C. Yen and R. Lee, A linear time algorithm to solve the weighted perfect domination problem in series-parallel
graphs, European J. Oper. Res., 73 (1994) 192–198.
[21] F. Zou, Y. Wang, X. H. Xu, X. Li, H. Du, P. Wan and W. Wu, New approximations for minimum-weighted
dominating sets and minimum-weighted connected dominating sets on unit disk graphs, Theor. Comput. Sci., 412
(2011) 198–208.

Files

History

  • Receive Date: 20 July 2017
  • Revise Date: 23 November 2019
  • Accept Date: 24 November 2019
  • Published Online: 01 March 2020

Share

How to cite

Statistics