فهرست مطالب نویسنده:
mohammadjavad hekmatnasab
-
Scientia Iranica, Volume:21 Issue: 6, 2014, PP 2142 -2152Spanners generated by the greedy algorithm{or greedy spanners{not only have good theoretical properties, like a linear number of edges, low degree and low weight, but previous experimental results also show that they are superior to spanners generated by other algorithms in practice. Because of the good properties of greedy spanners, they found several applications like in protein visualization. The major issue in computing greedy spanners is the high time and space complexity of algorithms that compute it. To construct the greedy spanner on a set of n points, the original greedy algorithm takes O(n3 log n) time. In 2005, an improvement was proposed by Farshi and Gudmundsson [Lecture Notes in Computer Science, Vol. 3669, pages 556{567] that works much faster in practice, but later it was shown that it has same theoretical time complexity. In 2008, Bose et al. [Lecture Notes in Computer Science, Vol. 5124, pages 390{401] discovered a near-quadratic time algorithm for constructing greedy spanners. In this paper, we compare time complexity of these three algorithms for computing the greedy spanner in practice.Keywords: geometric networks, Euclidean graphs, geometric spanners, greedy algorithm, greedy spanner
بدانید!
- در این صفحه نام مورد نظر در اسامی نویسندگان مقالات جستجو میشود. ممکن است نتایج شامل مطالب نویسندگان هم نام و حتی در رشتههای مختلف باشد.
- همه مقالات ترجمه فارسی یا انگلیسی ندارند پس ممکن است مقالاتی باشند که نام نویسنده مورد نظر شما به صورت معادل فارسی یا انگلیسی آن درج شده باشد. در صفحه جستجوی پیشرفته میتوانید همزمان نام فارسی و انگلیسی نویسنده را درج نمایید.
- در صورتی که میخواهید جستجو را با شرایط متفاوت تکرار کنید به صفحه جستجوی پیشرفته مطالب نشریات مراجعه کنید.