On Representing the Degree Sequences of Sublogarithmic-Degree Wheeler Graphs
On Representing the Degree Sequences of Sublogarithmic-Degree Wheeler Graphs
复制标题
关于次对数度惠勒图的度数列的表示
DOI：
10.1007/978-3-031-20643-6_18
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
T. Gagie
中科院分区：
文献类型：
--
作者：
T. Gagie
我们展示了如何为静态序列存储具有恒定查询时间的部分和数据结构\Documentclass[12pt]{Minimal}\usepackage{amsath}\usepackage{wa ysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{upgreek}\setlong{\oddsidemargin}{-69pt}\Begin{Document}$$o\Left(\frac{\log n}}(\log\log n)^2}\右)$$\end{文档}，在o\Left(\frac{\log n}{(\log\log n)^2}\$\end{Document}中)$\end{Document}$\end{Document}中由此推论，如果一个Wheeler图的顶点在\Docentclass[12pt]{Minimum}\usepackage{amsath}\usepackage{wa ysym}\usepackage{amsfonts}\usepackage{amsbsy}\usepackage{matrsfs}\usepackage{upgreek}\setlong{\oddsidemargin}{-69pt}\Begin{Document}$$o\Left(\frac{\log n}{(\log\log n)^2}\right)$\end{Document}中具有最大度，然后我们可以存储它的入度和出度序列以及输入和比特，对于\DocentClass[12pt]{Minimum}\usepackage{amsath}\usepackage{wa ysym}\usepackage{amsfonts}\usepackage{amsbsy}\usepackage{mathsfs}\usepackage{upgreek}\setlong{\oddsidemargin}{-69pt}\Begin{Document}$$k\in o\Left(\frac{\log n}{(\log\log n)^2}\right)$\end{Document}，使得在图中查询它们以进行模式匹配需要恒定的时间。
We show how to store a searchable partial-sums data structure with constant query time for a static sequenceSofnpositive integers in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$o \left( \frac{\log n}{(\log \log n)^2} \right) $$\end{document}, inbits for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \in o \left( \frac{\log n}{(\log \log n)^2} \right) $$\end{document}. It follows that if a Wheeler graph onnvertices has maximum degree in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$o \left( \frac{\log n}{(\log \log n)^2} \right) $$\end{document}, then we can store its in- and out-degree sequencesandinandbits, for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \in o \left( \frac{\log n}{(\log \log n)^2} \right) $$\end{document}, such that querying them for pattern matching in the graph takes constant time.