Linear-Size hopsets with small hopbound, and constant-hopbound hopsets in RNC
Linear-Size hopsets with small hopbound, and constant-hopbound hopsets in RNC
复制标题
RNC 中具有小跳跃范围的线性大小跳跃集和恒定跳跃范围跳跃集
DOI：
10.1145/3323165.3323177
复制
发表时间：
2019
影响因子：
1.3
通讯作者：
Ofer Neiman
中科院分区：
文献类型：
--
作者：
Michael Elkin;Ofer Neiman
Hopsets are a fundamental graph-theoretic and graph-algorithmic construct, and they are widely used for distance-related problems in a variety of computational settings. Currently existing constructions of hopsets produce hopsets either with Ω(nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega (n \log n)$$\end{document} edges, or with a hopbound nΩ(1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n^{\Omega (1)}$$\end{document}. In this paper we devise a construction of linear-size hopsets with hopbound (ignoring the dependence on ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon $$\end{document}) (loglogn)loglogn+O(1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(\log \log n)^{\log \log n + O(1)}$$\end{document}. This improves the previous hopbound for linear-size hopsets almost exponentially. We also devise efficient implementations of our construction in PRAM and distributed settings. The only existing PRAM algorithm [19] for computing hopsets with a constant (i.e., independent of n) hopbound requires nΩ(1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n^{\Omega (1)}$$\end{document} time. We devise a PRAM algorithm with polylogarithmic running time for computing hopsets with a constant hopbound, i.e., our running time is exponentially better than the previous one. Moreover, these hopsets are also significantly sparser than their counterparts from [19]. We apply these hopsets to achieve the following online variant of shortest paths in the PRAM model: preprocess a given weighted graph within polylogarithmic time, and then given any query vertex v, report all approximate shortest paths from v in constant time. All previous constructions of hopsets require either polylogarithmic time per query or polynomial preprocessing time.
Hopsets are a fundamental graph-theoretic and graph-algorithmic construct, and they are widely used for distance-related problems in a variety of computational settings. Currently existing constructions of hopsets produce hopsets either with Ω(nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega (n \log n)$$\end{document} edges, or with a hopbound nΩ(1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n^{\Omega (1)}$$\end{document}. In this paper we devise a construction of linear-size hopsets with hopbound (ignoring the dependence on ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon $$\end{document}) (loglogn)loglogn+O(1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(\log \log n)^{\log \log n + O(1)}$$\end{document}. This improves the previous hopbound for linear-size hopsets almost exponentially. We also devise efficient implementations of our construction in PRAM and distributed settings. The only existing PRAM algorithm [19] for computing hopsets with a constant (i.e., independent of n) hopbound requires nΩ(1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n^{\Omega (1)}$$\end{document} time. We devise a PRAM algorithm with polylogarithmic running time for computing hopsets with a constant hopbound, i.e., our running time is exponentially better than the previous one. Moreover, these hopsets are also significantly sparser than their counterparts from [19]. We apply these hopsets to achieve the following online variant of shortest paths in the PRAM model: preprocess a given weighted graph within polylogarithmic time, and then given any query vertex v, report all approximate shortest paths from v in constant time. All previous constructions of hopsets require either polylogarithmic time per query or polynomial preprocessing time.
通过低跳模拟器并行近似无向最短路径
DOI：
10.1145/3357713.3384321
发表时间：
2020
期刊：
Symposium on Theory of Computing (STOC
影响因子：
--
作者：
Andoni, Alexandr;Stein, Clifford;Zhong, Peilin
通讯作者：
Zhong, Peilin
次线性加法扳手下界的层次结构
DOI：
10.1137/1.9781611974782.36
发表时间：
2017
期刊：
SODA 2017
影响因子：
--
作者：
Abboud, Amir;Bodwin, Greg;Pettie, Seth
通讯作者：
Pettie, Seth