کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874256 | 686948 | 2015 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Computing the Gromov hyperbolicity of a discrete metric space
ترجمه فارسی عنوان
محاسبه هذلولی گراموف یک فضای متریک گسسته
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We give exact and approximation algorithms for computing the Gromov hyperbolicity of an n-point discrete metric space. We observe that computing the Gromov hyperbolicity from a fixed base-point reduces to a (max,min) matrix product. Hence, using the (max,min) matrix product algorithm by Duan and Pettie, the fixed base-point hyperbolicity can be determined in O(n2.69) time. It follows that the Gromov hyperbolicity can be computed in O(n3.69) time, and a 2-approximation can be found in O(n2.69) time. We also give a (2log2â¡n)-approximation algorithm that runs in O(n2) time, based on a tree-metric embedding by Gromov. We also show that hyperbolicity at a fixed base-point cannot be computed in O(n2.05) time, unless there exists a faster algorithm for (max,min) matrix multiplication than currently known.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issues 6â8, JuneâAugust 2015, Pages 576-579
Journal: Information Processing Letters - Volume 115, Issues 6â8, JuneâAugust 2015, Pages 576-579
نویسندگان
Hervé Fournier, Anas Ismail, Antoine Vigneron,