Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries
Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries
复制标题
定向动态图，及其在最大匹配和邻接查询中的应用
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
N. Zeh
中科院分区：
文献类型：
--
作者：
Meng He;Ganggui Tang;N. Zeh
我们考虑边定向问题，其目标是对一个具有\(n\)个顶点的无向动态图的边进行定向，使得顶点的出度有界，通常由图的树度的某个函数界定。我们的主要结果是表明，对于任何\(\beta\geq1\)，在平均每条边插入时间为\(O(\frac{\lg(n/(\beta\alpha))}{\beta})\)以及最坏情况下每条边删除时间为\(O(\beta\alpha)\)的情况下，可以维护一个\(O(\beta\alpha)\) - 定向，其中\(\alpha\)是更新过程中图的最大树度。这是通过对Brodal和Fagerberg[2]的算法进行新的分析实现的。不仅可以通过设置\(\beta\)的适当值表明这些界与Brodal和Fagerberg[2]以及Kowalik[7]中的分析相当，而且它还呈现了在先前工作中无法证明的权衡。它的主要应用是一种在平均更新时间为\(O(\alpha + \sqrt{\alpha\lg n})\)的情况下维护图的最大匹配的方法，这是目前对于树度较低的图在图算法的这个基本问题上的最佳结果。例如，当\(\alpha\)是一个常数（如平面图的情况）时，我们的工作表明可以在平均时间为\(O(\sqrt{\lg n})\)的情况下维护最大匹配，而之前的最佳方法需要平均时间为\(O(\frac{\lg n}{\lg\lg n})\) [13]。我们进一步设计了一种具有边定向最坏情况时间界的替代解决方案，并将其应用于在最大匹配和邻接查询方面取得新的结果。
We consider the problem of edge orientation, whose goal is to orient the edges of an undirected dynamic graph with (n) vertices such that vertex out-degrees are bounded, typically by a function of the graph’s arboricity. Our main result is to show that an (O(eta alpha ))-orientation can be maintained in (O(frac{lg (n/(eta alpha ))}{eta })) amortized edge insertion time and (O(eta alpha )) worst-case edge deletion time, for any (eta ge 1), where (alpha ) is the maximum arboricity of the graph during update. This is achieved by performing a new analysis of the algorithm of Brodal and Fagerberg [2]. Not only can it be shown that these bounds are comparable to the analysis in Brodal and Fagerberg [2] and that in Kowalik [7] by setting appropriate values of (eta ), it also presents tradeoffs that can not be proved in previous work. Its main application is an approach that maintains a maximal matching of a graph in (O(alpha + sqrt{alpha lg n})) amortized update time, which is currently the best result for graphs with low arboricity regarding this fundamental problem in graph algorithms. When (alpha ) is a constant which is the case with planar graphs, for instance, our work shows that a maximal matching can be maintained in (O(sqrt{lg n})) amortized time, while previously the best approach required (O(lg n / lg lg n)) amortized time [13]. We further design an alternative solution with worst-case time bounds for edge orientation, and applied it to achieve new results on maximal matchings and adjacency queries.