پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 158 |
| تعداد شماره‌ها | 6,230 |
| تعداد مقالات | 67,757 |
| تعداد مشاهده مقاله | 115,113,084 |
| تعداد دریافت فایل اصل مقاله | 89,877,031 |
$\alpha$-Gap Greedy Spanner | ||
| Journal of Algorithms and Computation | ||
| دوره 53، شماره 1، شهریور 2021، صفحه 41-60 اصل مقاله (420.08 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22059/jac.2021.81307 | ||
| نویسندگان | ||
| Hosein Salami1؛ Mostafa Nouri Baygi* 2 | ||
| 1Department of Computer Engineering, Ferdowsi University of Mashhad | ||
| 2Department of Computer Engineering, Ferdowsi University of Mashhad, Mashhad, Iran | ||
| چکیده | ||
| In this paper, we have introduced a new geometric spanner called $\alpha$-Gap greedy spanner, which is a parametric approximation of the well-known Gap-greedy spanner. We will show theoretically and experimentally that this spanner is similar to the Gap-greedy spanner in terms of qualitative features such as weight and maximum degree of vertices. %Wehave shown that this spanner can be computed in $O(n^2 \log n)$ time with$O(n)$ space, and $O(n \log n)$ expected time on the set of points placedrandomly in a unit square. Two algorithms have been proposed with running time $O(n^2 \log n)$ for constructing the $\alpha$-Gap greedy spanner. Space complexity of the first algorithm is $O(n^2)$, but it is reduced to $O(n)$ in the second one. %The proposed algorithms have a parameter, called $\alpha$, by which the similarity of the $\alpha$-Gap greedy spanner to the Gap-greedy spanner, in terms of quality features mentioned above, can be determined. Also, we have shown on the points placed randomly in a unit square, the $\alpha$-Gap greedy spanner can be constructed in the expected $O(n \log n)$ time. | ||
| کلیدواژه‌ها | ||
| computational geometry؛ geometric spanners؛ gap greedy spanner؛ construction algorithms؛ algorithm complexity | ||
|
آمار تعداد مشاهده مقاله: 277 تعداد دریافت فایل اصل مقاله: 219 |
||