پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 43 |
| تعداد شمارهها | 1,682 |
| تعداد مقالات | 13,762 |
| تعداد مشاهده مقاله | 32,194,128 |
| تعداد دریافت فایل اصل مقاله | 12,745,955 |
A linear algorithm for computing $\gamma_{_{[1,2]}}$-set in generalized series-parallel graphs | ||
| Transactions on Combinatorics | ||
| مقاله 1، دوره 9، شماره 1، خرداد 2020، صفحه 1-24 اصل مقاله (720.72 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2019.105482.1509 | ||
| نویسندگان | ||
| Pouyeh Sharifani؛ Mohammad Reza Hooshmandasl* | ||
| Department of Computer Science, Yazd University, Yazd, Iran | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| Domination؛ Total Domination؛ [1؛ Total [1؛ 2]-set؛ Series-parallel graphs؛ Generalized series-parallel graph | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 335 تعداد دریافت فایل اصل مقاله: 314 |
||