آمار
| تعداد نشریات | 7 |
| تعداد شماره‌ها | 77 |
| تعداد مقالات | 707 |
| تعداد مشاهده مقاله | 681,776 |
| تعداد دریافت فایل اصل مقاله | 493,818 |
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 | ||
|
آمار تعداد مشاهده مقاله: 832 تعداد دریافت فایل اصل مقاله: 480 |
||
