سامانه پشتیبانی خدمات اطلاعات

  اخبار و اعلانات

 آمار

تعداد نشریات161
تعداد شماره‌ها6,573
تعداد مقالات71,037
تعداد مشاهده مقاله125,521,052
تعداد دریافت فایل اصل مقاله98,780,628
Mesrikhani, Amir, Farshi, Mohammad, Iranfar, Behnam. (1398). Minimum Spanning Tree of Imprecise Points Under $L_1$-metric. , 51(2), 99-110. doi: 10.22059/jac.2019.75187
Amir Mesrikhani; Mohammad Farshi; Behnam Iranfar. "Minimum Spanning Tree of Imprecise Points Under $L_1$-metric". , 51, 2, 1398, 99-110. doi: 10.22059/jac.2019.75187
Mesrikhani, Amir, Farshi, Mohammad, Iranfar, Behnam. (1398). 'Minimum Spanning Tree of Imprecise Points Under $L_1$-metric', , 51(2), pp. 99-110. doi: 10.22059/jac.2019.75187
Mesrikhani, Amir, Farshi, Mohammad, Iranfar, Behnam. Minimum Spanning Tree of Imprecise Points Under $L_1$-metric. , 1398; 51(2): 99-110. doi: 10.22059/jac.2019.75187

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
آمار
تعداد مشاهده مقاله: 411
تعداد دریافت فایل اصل مقاله: 268





سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب