"Dynamic Graph Algorithms 001.ps.gz" - читать интересную книгу автораDynamic Graph Algorithms David Eppstein\Lambda Zvi Galily Giuseppe F. Italianoz 1 Introduction In many applications of graph algorithms, including communication networks, graphics, assembly planning, and VLSI design, graphs are subject to discrete changes, such as additions or deletions of edges or vertices. In the last decade there has been a growing interest in such dynamically changing graphs, and a whole body of algorithms and data structures for dynamic graphs has been discovered. This chapter is intended as an overview of this field. In a typical dynamic graph problem one would like to answer queries on graphs that are undergoing a sequence of updates, for instance, insertions and deletions of edges and vertices. The goal of a dynamic graph algorithm is to update efficiently the solution of a problem after dynamic changes, rather than having to recompute it from scratch each time. Given their powerful versatility, it is not surprising that dynamic algorithms and dynamic data structures are often more difficult to design and analyze than their static counterparts. We can classify dynamic graph problems according to the types of updates allowed. A problem is said to be fully dynamic if the update operations include unrestricted insertions and deletions of edges. A problem is called partially dynamic if only one type of update, either insertions or deletions, is allowed. If only insertions are allowed, the problem is called incremental; if only deletions are allowed it is called decremental. In this chapter, we focus our attention to dynamic algorithms for undirected graphs, which were studied more extensively than dynamic algorithms for directed graphs. Indeed, designing efficient fully dynamic data structures for directed graphs has turned out to be an extremely difficult task. \Lambda University of California, Irvine, CA 92717. Supported in part by NSF Grant CCR-9258355. yColumbia University, New York, NY 10027. Supported in part by NSF Grant CCR-9316209 and the CISE Institutional Infrastructure Grant CDA-9024735. zUniversity of Venice "Ca' Foscari", Venice, Italy. Supported in part by the ESPRIT LTR Project no. 20244 1 Most of the efficient data structures available for directed graphs are partially dynamic [2, 13, 29, 30, 31, 37, 39, 43, 53], and only preliminary results are available for fully dynamic problems [25]. For this reason, an alternative viewpoint that has been proposed is to measure the complexity of a dynamic algorithm as a function of the output change [17, 40]. The main dynamic problems considered on directed graphs include shortest paths and transitive closure. For lack of space, we do not include in this chapter dynamic algorithms for planar graphs, which have received considerable attention in recent years [6, 7, 11, 12, 18, 21, 22, 28, 32, 34, 42, 46, 47, 48, 51], and focus our attention to general undirected graphs only. The remainder of the chapter is organized as follows. In Section 2 we give some preliminary definitions and a little terminology. Dynamic tree problems are considered in Section 3, while in Section 4 we describe partially dynamic algorithms for undirected graphs. Fully dynamic algorithms for undirected graphs are described in Section 5. Finally, in Section 6 we describe some open problems. 2 Preliminary Definitions Given an undirected graph G with non-negative edge weights, the minimum spanning forest of G is the subgraph of minimum total weight that has the same connected components as the original graph. Whenever G is connected, this forest consists of a unique tree, and we refer to this tree as a minimum spanning tree of G. Note that a minimum spanning forest, or a mininum spanning tree is not necessarily unique. It is well known that a minimum spanning forest can be computed by either of two dual greedy algorithms, based on the following properties: Cut Property: Add edges one at a time to the spanning forest until it spans the graph. At each step, find a cut in the graph that contains no edges of the current forest, and add the edge with lowest weight crossing the cut. Cycle Property: Remove edges one at a time from the graph until only a forest is left. At each step, find a cycle in the remaining graph and remove the edge with the highest weight in the cycle. Given an undirected graph G = (V; E), and an integer k * 2, a pair of vertices hu; vi is said to be k-edge-connected if the removal of any (k \Gamma 1) edges in G leaves u and v connected. This is an |
|
|