Dynamic Trees:ET Trees.

By -

ET Trees

ET trees, first introduced in [18], have been later used to design algorithms for a variety of problems on dynamic graphs, such as fully dynamic connectivity and bipartiteness (see, ., [10, 13]).

They provide an implicit representation of dynamic forests whose vertices are associated with weighted or unweighted keys. In addition to arbitrary edge insertions and deletions, updates allow it to add or remove the weighted key associated to a vertex.

Supported queries are the following:

• connected(u, v): tells whether vertices u and v are in the same tree.

• size(v): returns the number of vertices in the tree that contains v.

• minkey(v): returns a key of minimum weight in the tree that contains v; if keys are unweighted, an arbitrary key is returned.

The main concept for the definition of ET trees is that of Euler tour.

DEFINITION 35.4 An Euler tour of a tree T is a maximal closed walk over the graph obtained by replacing each edge of T by two directed edges with opposite direction.

The Euler tour of a tree can be easily computed in linear time by rooting the tree at an arbitrary vertex and running a depth first visit [4]. Each time a vertex v is encountered on the walk, we call this an occurrence of v and we denote it by o(v). A vertex of degree ∆ has exactly ∆ occurrences, expect for the root which is visited ∆ + 1 times. Furthermore, the walk traverses each directed edge exactly once; hence, if T has n vertices, the Euler tour has length 2n − 2. Given an n-vertex tree T , we encode it with a sequence of 2n − 1 symbols given by an Euler tour. We refer to this encoding as ET (T ). For instance, the encoding of the tree given in Figure 35.7 derived from the Euler tour shown below the tree itself is ET (T ) = a b c b d b g f g e g b a.

DEFINITION 35.5 An ET tree is a dynamic balanced d-ary tree over some Euler tour around T . Namely, the leaves of the ET tree are the nodes of the Euler tour, in the same order in which they appear (see Figure 35.7).

An ET tree has O(n) nodes due to the linear length of the Euler tour and to properties of d-ary trees. However, since each vertex of T may occur several times in the Euler tour, an arbitrary occurrence is marked as representative of the vertex.

Updates

We first analyze how to update the encoding ET (T ) when T is subject to dynamic edge operations. If an edge e = (u, v) is deleted from T , denote by Tu and Tv the two trees

image

Applications

The query connected(u, v) can be easily supported in time O(log n/d) by finding the roots of the ET trees containing u and v and checking if they coincide. The same time is sufficient to check whether one element precedes another element in the ordering.

To support size and minkey queries, each node q of the ET tree maintains two additional values: the number s(q) of representatives below it and the minimum weight key k(q) attached to a representative below it. Such values can be easily maintained during updates and allow it to answer queries of the form size(v) and minkey(v) in O(log n/d) time for any vertex v of the forest: the root r of the ET tree containing v is found and values s(r) and k(r) are returned, respectively. details of the method.

We refer the interested reader to [10] for additional In Section 36.4 we will see how ET trees have been used [10, 11] to design a polyloga- rithmic algorithm for fully dynamic connectivity. Here we limit to observe that trees in a spanning forest of the dynamic graph are maintained using the Euler tour data structure, and therefore updates and connectivity queries within the forest can be supported in logarithmic time. The use of randomization and of a logarithmic decomposition makes it possible to maintain also non-tree edges in polylogarithmic time upon changes in the graph.

Comments

Post a Comment

Popular posts from this blog

0/1 Knapsack Problem Memory function.

By -
Image
0 / 1 Knapsack Problem Memory function Definition: Given a set of n items of known weights w1,…,wn and values v1,…,vn and a knapsack of capacity W, the problem is to find the most valuable subset of the items that fit into the knapsack. Knapsack problem is an OPTIMIZATION PROBLEM Dynamic programming approach to solve knapsack problem Step 1: Identify the smaller sub-problems. If items are labeled 1..n, then a sub-problem would be to find an optimal solution for Sk = {items labeled 1, 2, .. k } Step 2: Recursively define the value of an optimal solution in terms of solutions to smaller problems. Initial conditions: S te p 3: Bottom up computation using iteration Question: Apply bottom-up dynamic programming algorithm to the following instance of the knapsack problem Capacity W= 5 Solution: Using dynamic programming approach, we have: What is the composition of the optimal subset? The composition of the optimal subset if found by tracing back the computations for the...
Read more

Binary Space Partitioning Trees:BSP Tree as a Hierarchy of Regions.

By -
Image
BSP Tree as a Hierarchy of Regions Another way to look at BSP Trees is to focus on the hierarchy of regions created by the recursive partitioning, instead of focusing on the hyperplanes themselves. This view helps us to see more easily how intersections are efficiently computed. The key idea is to think of a BSP Tree region as serving as a bounding volume: each node v corresponds to a convex volume that completely contains all the geometry represented by the sub tree rooted at v . Therefore, if some other geometric entity, such as a point, ray, object, etc., is found to not intersect the bounding volume, then no intersection computations need be performed with any geometry within that volume. Consider as an example a situation in which we are given some test point and we want to find which object if any this point lies in. Initially, we know only that the point lies somewhere space ( Figure 20.12). By comparing the location of the point with respect to the first partitioning hyper pl...
Read more

Warshall’s Algorithm -to find TRANSITIVE CLOSURE

By -
Image
Warshall’s Algorithm -to find TRANSITIVE CLOSURE Some useful definitions: • D irected Graph: A graph whose every edge is directed is called directed graph OR digraph • A d j acency matrix: The adjacency matrix A = {aij} of a directed graph is the boolean matrix that has o 1 - if there is a directed edge from ith vertex to the jth vertex o 0 - Otherwise • T r ansitive Closure: Transitive closure of a directed graph with n vertices can be defined as the n-by-n matrix T={tij}, in which the elements in the ith row (1≤ i ≤ n) and the jth column(1≤ j ≤ n) is 1 if there exists a nontrivial directed path (i.e., a directed path of a positive length) from the ith vertex to the jth vertex, otherwise tij is 0. The transitive closure provides reach ability information about a digraph. Computing Transitive Closure: • We can perform DFS/BFS starting at each vertex • Performs traversal starting at the ith vertex. • Gives information about the vertices reachable from the ith vertex • Dr a...
Read more