پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 158 |
| تعداد شماره‌ها | 6,225 |
| تعداد مقالات | 67,685 |
| تعداد مشاهده مقاله | 114,971,902 |
| تعداد دریافت فایل اصل مقاله | 89,643,241 |
Minimum Spanning Tree of Imprecise Points Under $L_1$-metric | ||
| Journal of Algorithms and Computation | ||
| مقاله 9، دوره 51، شماره 2، اسفند 2019، صفحه 99-110 اصل مقاله (295.87 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22059/jac.2019.75187 | ||
| نویسندگان | ||
| Amir Mesrikhani* 1؛ Mohammad Farshi2؛ Behnam Iranfar2 | ||
| 1Yazd university | ||
| 2Department of Computer Science, Yazd University, Yazd, Iran | ||
| چکیده | ||
| Let $S$ be a set of imprecise points that is represented by axis-aligned pairwise disjoint squares in the plane. A precise instance of $S$ is a set of points, one from each region of $S$. In this paper, we study the optimal minimum spanning tree (\textit{OptMST}) problem on $S$. The \textit{OptMST} problem looks for the precise instance of $S$ such that the weight of the MST in this instance, maximize (Max-MST) or minimize (Min-MST) between all precise instances of~$S$ under $L_1$-metric. We present a $(\frac{3}{7})$-approximation algorithm for Max-MST. This is an improvement on the best-known approximation factor of $1/3$. If $S$ satisfies $k$-separability property (the distance between any pair of squares are at least $k.a_{max}$ where $a_{max}$ is the maximum length of the squares), the factor parameterizes to $\frac{2k+3}{2k+7}$. We propose a new lower bound for Min-MST problem on $S$ under $L_1$-metric where $S$ contains unit squares and provide an approximation algorithm with $(1+2\sqrt{2})$ asymptotic factor. | ||
| کلیدواژه‌ها | ||
| Minimum spanning tree؛ Imprecise point set؛ Approximation algorithm | ||
|
آمار تعداد مشاهده مقاله: 345 تعداد دریافت فایل اصل مقاله: 205 |
||