Average-Case Analysis of Dynamic Graph Algorithms
Average-Case Analysis of Dynamic Graph Algorithms
复制标题
动态图算法的平均情况分析
DOI：
10.1007/pl00009186
复制
发表时间：
1995
期刊：
影响因子：
1.1
通讯作者：
Monika Henzinger
中科院分区：
文献类型：
--
作者：
David Alberts;Monika Henzinger
抽象的。我们提出了一个模型，在动态图算法的边缘更新与限制的随机性和一般技术分析的预期运行时间的更新操作。该模型能够捕获许多应用中的平均情况，因为（1）它允许对可用于插入的边的集合的限制，以及（2）每个更新操作的类型（插入或删除）是任意的，即，不是随机的我们使用我们的技术来分析现有的和新的动态算法，为以下问题：最大基数匹配，最小生成森林，连接，2-边连接，k -边连接，k -顶点连接，和biparteness。给定一个随机图G，它有m条边和n个顶点，有l个更新操作序列，使得图在操作i之后包含mi条边，则对任意l执行更新的预期时间为：
$O（l log n + \sum_{i=1}^{l} n/\sqrt m_i）$在最小生成森林、连通性、2-边连通性和二分性的情况下。在最大匹配的情况下，每个更新操作的预期时间是O（n）。我们也给出了改进的k -边和k -点连通度的界.此外，我们给出了一个最大基数匹配的插入算法，最坏情况下每次插入的摊销时间为O（n）。
Abstract. We present a model for edge updates with restricted randomness in dynamic graph algorithms and a general technique for analyzing the expected running time of an update operation. This model is able to capture the average case in many applications, since (1) it allows restrictions on the set of edges which can be used for insertions and (2) the type (insertion or deletion) of each update operation is arbitrary, i.e., not random. We use our technique to analyze existing and new dynamic algorithms for the following problems: maximum cardinality matching, minimum spanning forest, connectivity, 2-edge connectivity, k -edge connectivity, k -vertex connectivity, and bipartiteness. Given a random graph G with m0 edges and n vertices and a sequence of l update operations such that the graph contains mi edges after operation i , the expected time for performing the updates for any l is
$O(l log n + \sum_{i=1}^{l} n/\sqrt m_i)$ in the case of minimum spanning forests, connectivity, 2-edge connectivity, and bipartiteness. The expected time per update operation is O(n) in the case of maximum matching. We also give improved bounds for k -edge and k -vertex connectivity. Additionally we give an insertions-only algorithm for maximum cardinality matching with worst-case O(n) amortized time per insertion.