Compact separator decompositions in dynamic trees and applications to labeling schemes

This paper presents an efficient scheme maintaining a separator decomposition representation in dynamic trees using asymptotically optimal labels. In order to maintain the short labels, the scheme uses relatively low message complexity. In particular, if the initial dynamic tree contains only the root, then the scheme incurs an O(log⁴ n) amortized message complexity per topology change, where n is the current number of vertices in the tree. As a separator decomposition is a fundamental decomposition of trees used extensively as a component in many static graph algorithms, our dynamic scheme for separator decomposition may be used for constructing dynamic versions to these algorithms. The paper then shows how to use our dynamic separator decomposition to construct efficient labeling schemes on dynamic trees, using the same message complexity as our dynamic separator scheme. Specifically, we construct efficient routing schemes on dynamic trees, for both the designer and the adversary port models, which maintain optimal labels, up to a multiplicative factor of O(log log n). In addition, it is shown how to use our dynamic separator decomposition scheme to construct dynamic labeling schemes supporting the ancestry and NCA relations using asymptotically optimal labels, as well as to extend a known result on dynamic distance labeling schemes. Supported in part at the Technion by an Aly Kaufman fellowship. Supported in part by a grant from the Israel Science Foundation.     

General compact labeling schemes for dynamic trees

Let F be a function on pairs of vertices. An F-labeling scheme is composed of a marker algorithm for labeling the vertices of a graph with short labels, coupled with a decoder algorithm allowing one to compute F(u, v) for any two vertices u and v directly from their labels. As applications for labeling schemes concern mainly large and dynamically changing networks, it is of interest to study distributed dynamic labeling schemes. This paper investigates labeling schemes for dynamic trees. We consider two dynamic tree models, namely, the leaf-dynamic tree model in which at each step a leaf can be added to or removed from the tree and the leaf-increasing tree model in which the only topological event that may occur is that a leaf joins the tree. A general method for constructing labeling schemes for dynamic trees (under the above mentioned dynamic tree models) was previously developed in Korman et al. (Theory Comput Syst 37:49–75, 2004). This method is based on extending an existing static tree labeling scheme to the dynamic setting. This approach fits many natural functions on trees, such as distance, separation level, ancestry relation, routing (in both the adversary and the designer port models), nearest common ancestor etc.. Their resulting dynamic schemes incur overheads (over the static scheme) on the label size and on the communication complexity. In particular, all their schemes yield a multiplicative overhead factor of Ω(log n) on the label sizes of the static schemes. Following (Korman et al., Theory Comput Syst 37:49–75, 2004), we develop a different general method for extending static labeling schemes to the dynamic tree settings. Our method fits the same class of tree functions. In contrast to the above paper, our trade-off is designed to minimize the label size, sometimes at the expense of communication. Informally, for any function k(n) and any static F-labeling scheme on trees, we present an F-labeling scheme on dynamic trees incurring multiplicative overhead factors (over the static scheme) of on the label size and on the amortized message complexity. In particular, by setting for any , we obtain dynamic labeling schemes with asymptotically optimal label sizes and sublinear amortized message complexity for the ancestry relation, the id-based and label-based nearest common ancestor relation and the routing function. Supported in part at the Technion by an Aly Kaufman fellowship.     

Optimal point removal in closed-2PM labeling

An optimal labeling where labels are disjoint axis-parallel equal-size squares is called 2PM labeling if the labels have maximum length each attached to its corresponding point on the middle of one of its horizontal edges. In a closed-2PM labeling, no two edges of labels containing points should intersect. Removing one point and its label, makes free room for its adjacent labels and may cause a global label expansion. In this paper, we construct several data structures in the preprocessing stage, so that any point removal event is handled efficiently. We present an algorithm which decides in O(lgn) amortized time whether a label removal leads to label expansion in which case a new optimal labeling for the remaining points is generated in O(n) amortized time.     

Decremental 2- and 3-connectivity on planar graphs

We study the problem of maintaining the 2-edge-, 2-vertex-, and 3-edge-connected components of a dynamic planar graph subject to edge deletions. The 2-edge-connected components can be maintained in a total ofO(n logn) time under any sequence of at mostO(n) deletions. This givesO(logn) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total ofO(n log² n) time. This givesO(log² n) amortized time per deletion. The space required by all our data structures isO(n). All our time bounds improve previous bounds.This work was partially supported by the ESPRIT II Basic Research Actions Program of the EC under Project ALCOM II (contract No. 7141) and Project ASMICS. A preliminary version of this paper appears in [12].Partially supported by a CNR Fellowship. Work done while the author was visiting Columbia University.On leave from IBM T. J. Watson Research Center, Yorktown Heights, NY 10598, USA.     

On Parallel Selection and Searching in Partial Orders: Sorted Matrices

Parallel algorithms for the problems of selection and searching on sorted matrices are formulated. The selection algorithm takesO(lognlog lognlog*n) time withO(n/lognlog*n) processors on an EREW PRAM. This algorithm can be generalized to solve the selection problem on a set of sorted matrices. The searching algorithm takesO(log logn) time withO(n/log logn) processors on a Common CRCW PRAM, which is optimal. We show that no algorithm using at mostnlog^cnprocessors,c≥ 1, can solve the matrix search problem in time faster than Ω(log logn) and that Ω(logn) steps are needed to solve this problem on any model that does not allow concurrent writes.     

Distributed verification of minimum spanning trees

The problem of verifying a Minimum Spanning Tree (MST) was introduced by Tarjan in a sequential setting. Given a graph and a tree that spans it, the algorithm is required to check whether this tree is an MST. This paper investigates the problem in the distributed setting, where the input is given in a distributed manner, i.e., every node “knows” which of its own emanating edges belong to the tree. Informally, the distributed MST verification problem is the following. Label the vertices of the graph in such a way that for every node, given (its own state and label and) the labels of its neighbors only, the node can detect whether these edges are indeed its MST edges. In this paper, we present such a verification scheme with a maximum label size of O(log n log W), where n is the number of nodes and W is the largest weight of an edge. We also give a matching lower bound of Ω(log n log W) (as long as W > (log n)^1+ε for some fixed ε > 0). Both our bounds improve previously known bounds for the problem. For the related problem of tree sensitivity also presented by Tarjan, our method yields rather efficient schemes for both the distributed and the sequential settings. A preliminary version of this work was presented in ACM PODC 2006. A. Korman was supported in part at the Technion by an Aly Kaufman fellowship. S. Kutten was supported in part by a grant from the Israeli Ministry for Science and Technology.     

Labeling Points with Weights

Annotating maps, graphs, and diagrams with pieces of text is an important step in information visualization that is usually referred to as label placement. We define nine label-placement models for labeling points with axis-parallel rectangles given a weight for each point. There are two groups: fixed-position models and slider models. We aim to maximize the weight sum of those points that receive a label. We first compare our models by giving bounds for the ratios between the weights of maximum-weight labelings in different models. Then we present algorithms for labeling n points with unit-height rectangles. We show how an O(n\log n)-time factor-2 approximation algorithm and a PTAS for fixed-position models can be extended to handle the weighted case. Our main contribution is the first algorithm for weighted sliding labels. Its approximation factor is (2+\varepsilon), it runs in O(n ²/\varepsilon) time and uses O(n/\varepsilon) space. We show that other than for fixed-position models even the projection to one dimension remains NP-hard. For slider models we also investigate some special cases, namely (a) the number of different point weights is bounded, (b) all labels are unit squares, and (c) the ratio between maximum and minimum label height is bounded.     

Labeling Points with Weights

Annotating maps, graphs, and diagrams with pieces of text is an important step in information visualization that is usually referred to as label placement. We define nine label-placement models for labeling points with axis-parallel rectangles given a weight for each point. There are two groups: fixed-position models and slider models. We aim to maximize the weight sum of those points that receive a label. We first compare our models by giving bounds for the ratios between the weights of maximum-weight labelings in different models. Then we present algorithms for labeling n points with unit-height rectangles. We show how an O(n\log n)-time factor-2 approximation algorithm and a PTAS for fixed-position models can be extended to handle the weighted case. Our main contribution is the first algorithm for weighted sliding labels. Its approximation factor is (2+\varepsilon), it runs in O(n ²/\varepsilon) time and uses O(n/\varepsilon) space. We show that other than for fixed-position models even the projection to one dimension remains NP-hard. For slider models we also investigate some special cases, namely (a) the number of different point weights is bounded, (b) all labels are unit squares, and (c) the ratio between maximum and minimum label height is bounded.     

Informative labeling schemes for graphs

This paper introduces the notion of informative labeling schemes for arbitrary graphs. Let f(W) be a function on subsets of vertices W. An f labeling scheme labels the vertices of a weighted graph G in such a way that f(W) can be inferred (or at least approximated) efficiently for any vertex subset W of G by merely inspecting the labels of the vertices of W, without having to use any additional information sources.A number of results illustrating this notion are presented in the paper. We begin by developing f labeling schemes for three functions f over the class of n-vertex trees. The first function, SepLevel, gives the separation level of any two vertices in the tree, namely, the depth of their least common ancestor. The second, LCA, provides the least common ancestor of any two vertices. The third, Center, yields the center of any three given vertices v₁,v₂,v₃ in the tree, namely, the unique vertex z connected to them by three edge-disjoint paths. All of these three labeling schemes use O-bit labels, which is shown to be asymptotically optimal.Our main results concern the function Steiner(W), defined for weighted graphs. For any vertex subset W in the weighted graph G, Steiner(W) represents the weight of the Steiner tree spanning the vertices of W in G. Considering the class of n-vertex trees with M-bit edge weights, it is shown that for this class there exists a Steiner labeling scheme using O((M+logn)logn) bit labels, which is asymptotically optimal. It is then shown that for the class of arbitrary n-vertex graphs with M-bit edge weights, there exists an approximate-Steiner labeling scheme, providing an estimate (up to a factor of O(logn)) for the Steiner weight Steiner(W) of a given set of vertices W, using O bit labels.     

A new scheme for the deterministic simulation of PRAMs in VLSI

A deterministic scheme for the simulation of (n, m)-PRAM computation is devised. Each PRAM step is simulated on a bounded degree network consisting of a mesh-of-trees (MT) of siden. The memory is subdivided inn modules, each local to a PRAM processor. The roots of the MT contain these processors and the memory modules, while the otherO(n ²) nodes have the mere capabilities of packet switchers and one-bit comparators. The simulation algorithm makes a crucial use of pipelining on the MT, and attains a time complexity ofO(log² n/log logn). The best previous time bound wasO(log² n) on a different interconnection network withn processors. While the previous simulation schemes use an intermediate MPC model, which is in turn simulated on a bounded degree network, our method performs the simulation directly with a simple algorithm.This work has been supported in part by Ministero della Pubblica Istruzione of Italy under a research grant.     

A better performance guarantee for approximate graph coloring

Approximate graph coloring takes as input a graph and returns a legal coloring which is not necessarily optimal. We improve the performance guarantee, or worst-case ratio between the number of colors used and the minimum number of colors possible, toO(n(log logn)³/(logn)³), anO(logn/log logn) factor better than the previous best-known result.The work of the first author was supported by Air Force Grant AFOSR-86-0078 and NSF PYI Grant 8657527-CCR. The work of the second author was supported by a National Science Foundation Graduate Fellowship.     

A balanced search tree with O(1) worst-case update time

Summary In this paper a new data structure is described for performing member and neighbor queries in O(logn) time that allows for O(1) worst-case update time once the position of the inserted or deleted element is known. In this way previous solutions that achieved only O(1) amortized time or O(log^* n) worst-case time are improved. The method is based on a combinatorial result on the height of piles that are split after some fixed number of insertions. This combinatorial result is interesting in its own right and might have other applications as well.     

Stochastic analysis of a churn-tolerant structured peer-to-peer scheme

We present and analyze a simple and general scheme to build a churn (fault)-tolerant structured Peer-to-Peer (P2P) network. Our scheme shows how to “convert” a static network into a dynamic distributed hash table(DHT)-based P2P network such that all the good properties of the static network are guaranteed with high probability (w.h.p). Applying our scheme to a cube-connected cycles network, for example, yields a O(logN) degree connected network, in which every search succeeds in O(logN) hops w.h.p., using O(logN) messages, where N is the expected stable network size. Our scheme has an constant storage overhead (the number of nodes responsible for servicing a data item) and an O(logN) overhead (messages and time) per insertion and essentially no overhead for deletions. All these bounds are essentially optimal. While DHT schemes with similar guarantees are already known in the literature, this work is new in the following aspects: (1) It presents a rigorous mathematical analysis of the scheme under a general stochastic model of churn and shows the above guarantees; (2) The theoretical analysis is complemented by a simulation-based analysis that validates the asymptotic bounds even in moderately sized networks and also studies performance under changing stable network size; (3) The presented scheme seems especially suitable for maintaining dynamic structures under churn efficiently. In particular, we show that a spanning tree of low diameter can be efficiently maintained in constant time and logarithmic number of messages per insertion or deletion w.h.p.     

Connected component and simple polygon intersection searching

Efficient data structures are given for the following two query problems: (i) preprocess a setP of simple polygons with a total ofn edges, so that all polygons ofP intersected by a query segment can be reported efficiently, and (ii) preprocess a setS ofn segments, so that the connected components of the arrangement ofS intersected by a query segment can be reported quickly. In these problems we do not want to return the polygons or connected components explicitly (i.e., we do not wish to report the segments defining the polygon, or the segments lying in the connected components). Instead, we assume that the polygons (or connected components) are labeled and we just want to report their labels. We present data structures of sizeO(n ¹⁺) that can answer a query in timeO(n ¹⁺+k), wherek is the output size. If the edges ofP (or the segments inS) are orthogonal, the query time can be improved toO(logn+k) usingO(n logn) space. We also present data structures that can maintain the connected components as we insert new segments. For arbitrary segments the amortized update and query time areO(n ^1/2+) andO(n ^1/2++k), respectively, and the space used by the data structure isO(n ¹⁺. If we allowO(n ^4/3+ space, the amortized update and query time can be improved toO(n ^1/3+ andO(n ^1/3++k, respectively. For orthogonal segments the amortized update and query time areO(log² n) andO(log² n+klogn), and the space used by the data structure isO (n logn). Some other related results are also mentioned.Part of this work was done while the second author was visiting the first author on a grant by the Dutch Organization for Scientific Research (N.W.O.). The research of the second author was also supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). The research of the first author was supported by National Science Foundation Grant CCR-91-06514.     

Heuristic Contention-Free Broadcast in Heterogeneous Networks of Workstations with Multiple Send and Receive Speeds

This paper presents three efficient contention-free algorithms for broadcasting on heterogeneous networks of workstations (HNOW). In an HNOW, many different speed types of workstations can have distinct send and receive overhead. Previous research has shown that finding an optimal routing scheme in an HNOW is not easy [2,12], because properly arranging all workstations in the scheduling tree is difficult. Therefore, this investigation focuses mainly on enhancing the performance of an HNOW by properly arranging fastest nodes into the internal nodes of upper levels in the scheduling tree. Fastest node first is fundamental in designing an efficient algorithm. This paper presents three schemes called EBS, VBBS, and VBBSWF. All of these three schemes can be executed in O(n log(n)) time, where n is the number of workstations. They are all contention-free when broadcasting in an HNOW. Based on the simulation result, the proposed schemes outperform the broadcast with minimal steps [13] and the scheduling tree [22] generated by dynamic programing in an HNOW.     

Communication-Efficient Broadcasting in Complete Networks with Dynamic Faults

We consider the problem of message (and bit) efficient broadcasting in complete networks with dynamic faults. Despite the simplicity of the setting, the problem turned out to be surprisingly interesting from the algorithmic point of view. In this paper we show an Ω(n + t f ^{t/(t – 1)}) lower bound on the number of messages sent by any t-step broadcasting algorithm, where f is the number of faults per step. The core of the paper contains a constructive O(n + t f ^{(t + 1)/t} ) upper bound. The algorithms involved are of time complexity O(t), not strictly t. In addition, we present a bit-efficient algorithm of O(n log² n) bit and O(log n) time complexities. We also show that it is possible to achieve the same message complexity even if the nodes do not know the id’s of their neighbours, but instead have only a Weak Sense of Direction.     

A faster parallel algorithm for a matrix searching problem

We give an improved parallel algorithm for the problem of computing the tube minima of a totally monotonen ×n ×n matrix, an important matrix searching problem that was formalized by Aggarwal and Park and has many applications. Our algorithm runs inO(log logn) time withO(n²/log logn) processors in theCRCW-PRAM model, whereas the previous best ran inO((log logn)²) time withO(n²/(log logn)² processors, also in theCRCW-PRAM model. Thus we improve the speed without any deterioration in thetime ×processors product. Our improved bound immediately translates into improvedCRCW-PRAM bounds for the numerous applications of this problem, including string editing, construction of Huffmann codes and other coding trees, and many other combinatorial and geometric problems.This research was supported by the Office of Naval Research under Grants N00014-84-K-0502 and N00014-86-K-0689, the Air Force Office of Scientific Research under Grant AFOSR-90-0107, the National Science Foundation under Grant DCR-8451393, and the National Library of Medicine under Grant R01-LM05118. Part of the research was done while the author was at Princeton University, visiting the DIMACS center.     

Additive Spanners and Distance and Routing Labeling Schemes for Hyperbolic Graphs

δ-Hyperbolic metric spaces have been defined by M. Gromov in 1987 via a simple 4-point condition: for any four points u,v,w,x, the two larger of the distance sums d(u,v)+d(w,x),d(u,w)+d(v,x),d(u,x)+d(v,w) differ by at most?2δ. They play an important role in geometric group theory, geometry of negatively curved spaces, and have recently become of interest in several domains of computer science, including algorithms and networking. In this paper, we study unweighted δ-hyperbolic graphs. Using the Layering Partition technique, we show that every n-vertex δ-hyperbolic graph with δ≥1/2 has an additive O(δlog?n)-spanner with at most O(δn) edges and provide a simpler, in our opinion, and faster construction of distance approximating trees of δ-hyperbolic graphs with an additive error O(δlog?n). The construction of our tree takes only linear time in the size of the input graph. As a consequence, we show that the family of n-vertex δ-hyperbolic graphs with δ≥1/2 admits a routing labeling scheme with O(δlog?² n) bit labels, O(δlog?n) additive stretch and O(log?₂(4δ)) time routing protocol, and a distance labeling scheme with O(log?² n) bit labels, O(δlog?n) additive error and constant time distance decoder.     

Efficient parallel algorithms forr-dominating set andp-center problems on trees

We develop efficient parallel algorithms for ther-dominating set and thep-center problems on trees. On a concurrent-read exclusive-write PRAM, our algorithm for ther-dominating set problem runs inO(logn log logn) time withn processors. The algorithm for thep-center problem runs inO(log² n log logn) time withn processors.Xin He was supported in part by an Ohio State University Presidential Fellowship, and by the Office of Research and Graduate Studies of Ohio State University. Yaacov Yesha was supported in part by the National Science Foundation under Grant No. DCR-8606366.     

A better performance guarantee for approximate graph coloring

Approximate graph coloring takes as input a graph and returns a legal coloring which is not necessarily optimal. We improve the performance guarantee, or worst-case ratio between the number of colors used and the minimum number of colors possible, toO(n(log logn)³/(logn)³), anO(logn/log logn) factor better than the previous best-known result.