آمار
| تعداد نشریات | 5 |
| تعداد شماره‌ها | 112 |
| تعداد مقالات | 1,271 |
| تعداد مشاهده مقاله | 1,239,180 |
| تعداد دریافت فایل اصل مقاله | 1,098,517 |
Complexity and approximation ratio of semitotal domination in graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 3، دوره 3، شماره 2، اسفند 2018، صفحه 143-150 اصل مقاله (334.87 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2018.25987.1065 | ||
| نویسندگان | ||
| Zehui Shao* ؛ Pu Wu | ||
| Guangzhou University | ||
| چکیده | ||
| A set $S \subseteq V(G)$ is a semitotal dominating set of a graph $G$ if it is a dominating set of $G$ and every vertex in $S$ is within distance 2 of another vertex of $S$. The semitotal domination number $\gamma_{t2}(G)$ is the minimum cardinality of a semitotal dominating set of $G$. We show that the semitotal domination problem is APX-complete for bounded-degree graphs, and the semitotal domination problem in any graph of maximum degree $\Delta$ can be approximated with an approximation ratio of $2+\ln(\Delta-1)$. | ||
| کلیدواژه‌ها | ||
| semitotal domination؛ APX-complete؛ NP-completeness | ||
| مراجع | ||
|
[1] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi, Complexity and approximation, Springer, Berlin, 1999.
[2] L. Chen, W. Zeng, and C. Lu, Np-completeness and apx-completeness of restrained domination in graphs, Theoret. Comput. Sci. 448 (2012), 1–8.
[3] M.R. Garey and D.S. Johnson, Computers and intractability: A guide to the theory of npcompleteness (series of books in the mathematical sciences), ed, Computers and Intractability (1979), 340.
[4] W. Goddard, M.A. Henning, and C.A. McPillan, Semitotal domination in graphs, Util. Math. 94 (2014), 67–81.
[5] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[6] O. [Ore, Theory of graphs, vol. 38, American Mathematical Society, 1962.
[7] C.H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, J. Comput. System Sci. 43 (1991), no. 3, 425–440.
[8] E. Zhu, Z. Shao, and J. Xu, Semitotal domination in claw-free cubic graphs, Graphs Combin. 33 (2017), no. 5, 1119–1130. | ||
|
آمار تعداد مشاهده مقاله: 1,245 تعداد دریافت فایل اصل مقاله: 739 |
||