آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 131 |
| تعداد مقالات | 1,635 |
| تعداد مشاهده مقاله | 1,906,645 |
| تعداد دریافت فایل اصل مقاله | 1,764,448 |
Algorithmic Aspects of Independent Dominating Set in Grid Graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 21 آبان 1405 | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2026.31431.2848 | ||
| نویسندگان | ||
| Hamid Gholami1؛ Doost Ali Mojdeh* 1؛ Mahdi Imanparast2 | ||
| 1Department of Mathematics, Faculty of Mathematical Sciences, University of Mazandaran, Babolsar, Iran | ||
| 2Department of Computer Science, Faculty of Basic Sciences, University of Bojnord, Bojnord, Iran | ||
| چکیده | ||
| For a graph $G(V,E)$, a dominating set $D$ is defined as a subset $D \subseteq V$ such that every vertex in the graph is either included in $D$ or is adjacent to at least one vertex in $D$. A set $D\subseteq V$ of vertices is called an independent dominating set if $D$ is a dominating set and no two vertices in $D$ are adjacent. In this study, we present a $2$-approximation algorithm for computing an independent dominating set of grid graphs with a running time $O(n^2)$. Our proposed algorithm employs a greedy selection strategy that iteratively identifies vertices based on their potential to cover the maximum number of uncovered neighbors. We establish that our algorithm guarantees an approximation factor of $2$, meaning the number of vertices in the independent dominating set produced by the algorithm is at most twice the number of vertices in an optimal solution. | ||
| کلیدواژهها | ||
| Approximation algorithms؛ NP-hard problems؛ Grid graphs؛ Dominating sets؛ Independent dominating sets | ||
|
آمار تعداد مشاهده مقاله: 3 |
||