A note on maximum independent sets in rectangle intersection graphs

Finding the maximum independent set in the intersection graph of n axis-parallel rectangles is NP-hard. We re-examine two known approximation results for this problem. For the case of rectangles of unit height, Agarwal, van Kreveld and Suri [Comput. Geom. Theory Appl. 11 (1998) 209-218] gave a (1+1/k)-factor algorithm with an O(nlogn+n^2k−1) time bound for any integer constant k?1; we describe a similar algorithm running in only O(nlogn+nΔ^k−1) time, where Δ?n denotes the maximum number of rectangles a point can be in. For the general case, Berman, DasGupta, Muthukrishnan and Ramaswami [J. Algorithms 41 (2001) 443-470] gave a ⌈log_kn⌉-factor algorithm with an O(n^k+1) time bound for any integer constant k?2; we describe similar algorithms running in O(nlogn+nΔ^k−2) and n^O(k/logk) time.     

Parallel construction of binary trees with near optimal weighted path length

We present parallel algorithms to construct binary trees with almost optimal weighted path length. Specifically, assuming that weights are normalized (to sum up to one) and error refers to the (absolute) difference between the weighted path length of a given tree and the optimal tree with the same weights, we present anO (logn)-time andn(log lognl logn)-EREW-processor algorithm which constructs a tree with error less than 0.18, andO (k logn log^* n)-time andn-CREW-processor algorithm which produces a tree with error at most l/n ^k , and anO (k ² logn)-time andn ²-CREW-processor algorithm which produces a tree with error at most l/n ^k . As well, we describe two sequential algorithms, anO(kn)-time algorithm which produces a tree with error at most l/n ^k , and anO(kn)-time algorithm which produces a tree with error at most . The last two algorithms use different computation models.The first author's research was supported in part by NSERC Research Grant 3053. A part of this work was done while the second author was at the University of British Columbia.     

Smallest k-point enclosing rectangle and square of arbitrary orientation

Given a set of n points in 2D, the problem of identifying the smallest rectangle of arbitrary orientation, and containing exactly k(?n) points is studied in this paper. The worst case time and space complexities of the proposed algorithm are O(n²logn+nk(n−k)(n−k+logk)) and O(n), respectively. The algorithm is then used to identify the smallest square of arbitrary orientation, and containing exactly k points in O(n²logn+kn²(n−k)logn) time.     

Improved algorithm for the symmetry number problem on trees

The symmetry number of a tree is defined as the number of nodes of the maximum subtree of the tree that exhibits axial symmetry. The best previous algorithm for computing the symmetry number for an unrooted unordered tree is due to [P.P. Mitra, M.A.U. Abedin, M.A. Kashem, Algorithms for solving the symmetry number problem on trees, Inform. Process. Lett. 91 (2004) 163-169] and runs in O(n³) time. In this paper we show an improvement on this time complexity by encoding small trees. Our algorithm runs in time O(n³²(loglogn/logn)).     

Improved algorithm for all pairs shortest paths

We present an improved algorithm for all pairs shortest paths. For a graph of n vertices our algorithm runs in O(n³(loglogn/logn)^5/7) time. This improves the best previous result which runs in O(n³(loglogn/logn)^1/2) time.     

Primal-dual approximation algorithms for the Prize-Collecting Steiner Tree Problem

The primal-dual scheme has been used to provide approximation algorithms for many problems. Goemans and Williamson gave a (2−1/(n−1))-approximation for the Prize-Collecting Steiner Tree Problem that runs in O(n³logn) time—it applies the primal-dual scheme once for each of the n vertices of the graph. We present a primal-dual algorithm that runs in O(n²logn), as it applies this scheme only once, and achieves the slightly better ratio of (2−2/n). We also show a tight example for the analysis of the algorithm and discuss briefly a couple of other algorithms described in the literature.     

An analytic approach to the height of binary search trees

By using analytic tools it is shown that the expected value of the heightH _n of binary search trees of sizen is asymptotically given by EH _n =c logn+ (log logn) and its variance by VH _n = ((log logn)²), wherec=4.31107 …. The same bounds have been obtained by Devroye and Reed [3] by completely different methods. Dedicated to Philippe Flajolet on the occasion of his 50th birthday This research was supported by the Austrian Science Foundation FWF, Grant P10187-MAT. Online publication September 22, 2000.     

k-Restricted rotation distance between binary trees

The restricted rotation distancedR(S,T) between two binary trees S, T of n vertices is the minimum number of rotations to transform S into T, where rotations take place at the root of S, or at the right child of the root. A sharp upper bound dR(S,T)?4n−8 is known, based on group theory [S. Cleary, J. Taback, Bounding restricted rotation distance, Information Processing Letters 88 (5) (2003) 251-256]. We refine this bound to a sharp dR(S,T)?4n−8−ρS−ρT, where ρS and ρT are the numbers of vertices in the rightmost vertex chains of the two trees, using an elementary transformation algorithm. We then generalize the concept to k-restricted rotation, by allowing rotations to take place at all the vertices of the highest k levels of the tree, and study the new distance for k=2. The case k?3 is essentially open.     

ℓ 2 2 Spreading Metrics for Vertex Ordering Problems

We design approximation algorithms for the vertex ordering problems Minimum Linear Arrangement, Minimum Containing Interval Graph, and Minimum Storage-Time Product, achieving approximation factors of $O(\sqrt{\log n}\log\log n)We design approximation algorithms for the vertex ordering problems Minimum Linear Arrangement, Minimum Containing Interval Graph, and Minimum Storage-Time Product, achieving approximation factors of O(?{logn}loglogn)O(\sqrt{\log n}\log\log n) , O(?{logn}loglogn)O(\sqrt{\log n}\log\log n) , and O(?{logT}loglogT)O(\sqrt{\log T}\log\log T) , respectively, the last running in time polynomial in T (T being the sum of execution times). The technical contribution of our paper is to introduce “ℓ ₂² spreading metrics” (that can be computed by semidefinite programming) as relaxations for both undirected and directed “permutation metrics,” which are induced by permutations of {1,2,…,n}. The techniques introduced in the recent work of Arora, Rao and Vazirani (Proc. of 36th STOC, pp. 222–231, 2004) can be adapted to exploit the geometry of such ℓ ₂² spreading metrics, giving a powerful tool for the design of divide-and-conquer algorithms. In addition to their applications to approximation algorithms, the study of such ℓ ₂² spreading metrics as relaxations of permutation metrics is interesting in its own right. We show how our results imply that, in a certain sense we make precise, ℓ ₂² spreading metrics approximate permutation metrics on n points to a factor of O(?{logn}loglogn)O(\sqrt{\log n}\log\log n) .     

Selecting distances in the plane

We present a randomized algorithm for computing the kth smallest distance in a set ofn points in the plane, based on the parametric search technique of Megiddo [Mel]. The expected running time of our algorithm is O(n^4/3 log^8/3 n). The algorithm can also be made deterministic, using a more complicated technique, with only a slight increase in its running time. A much simpler deterministic version of our procedure runs in time O(n^3/2 log^5/2 n). All versions improve the previously best-known upper bound ofO(@#@ n^9/5 log^4/5 n) by Chazelle [Ch]. A simpleO(n logn)-time algorithm for computing an approximation of the median distance is also presented.Part of this work was done while the first two authors were visting DIMACS, Rutgers University, New Brunswick, NJ. Work by the first three authors has been partly supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center-NSF-STC88-09648. Work by the second author has also been supported by National Security Agency Grant MDA 904-89-H-2030. Work by the third author has also been supported by National Science Foundation Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, and the Fund for Basic Research administered by the Israeli Academy of Sciences.     

Efficient parallel algorithms for breadth first spanning forests of general graphs

Ghosh and Bhattacharjee propose [2] (Intern. J. Computer Math., 1984, Vol. 15, pp. 255-268) an algorithm of determining breadth first spanning trees for graphs, which requires that the input graphs contain some vertices, from which every other vertex in the input graph can be reached. These vertices are called starting vertices. The complexity of the GB algorithm is O(log² n) using O{n ³) processors. In this paper an algorithm, named BREADTH, also computing breadth first spanning trees, is proposed. The complexity is O(log² n) using O{n ³/logn) processors. Then an efficient parallel algorithm, named- BREADTHFOREST, is proposed, which generalizes algorithm BREADTH. The output of applying BREADTHFOREST to a general graph, which may not contain any starting vertices, is a breadth first spanning forest of the input graph. The complexity of BREADTHFOREST is the same as BREADTH.     

Towards optimal range medians

We consider the following problem: Given an unsorted array of n elements, and a sequence of intervals in the array, compute the median in each of the subarrays defined by the intervals. We describe a simple algorithm which needs O(nlogk+klogn) time to answer k such median queries. This improves previous algorithms by a logarithmic factor and matches a comparison lower bound for k=O(n). The space complexity of our simple algorithm is O(nlogn) in the pointer machine model, and O(n) in the RAM model. In the latter model, a more involved O(n) space data structure can be constructed in O(nlogn) time where the time per query is reduced to O(logn/loglogn). We also give efficient dynamic variants of both data structures, achieving O(log²n) query time using O(nlogn) space in the comparison model and O((logn/loglogn)²) query time using O(nlogn/loglogn) space in the RAM model, and show that in the cell-probe model, any data structure which supports updates in O(log^O(1)n) time must have Ω(logn/loglogn) query time.Our approach naturally generalizes to higher-dimensional range median problems, where element positions and query ranges are multidimensional—it reduces a range median query to a logarithmic number of range counting queries.     

Range mode and range median queries in constant time and sub-quadratic space

Given a list of n items and a function defined over sub-lists, we study the space required for computing the function for arbitrary sub-lists in constant time.For the function mode we improve the previously known space bound O(n²/logn) to O(n²loglogn/log²n) words.For median the space bound is improved to O(n²loglog²n/log²n) words from O(n²⋅log(k)n/logn), where k is an arbitrary constant and log(k) is the iterated logarithm.     

Compact searchable static binary trees

A compact searchable representation of static binary trees is presented that can be traversed in O(h) time where h is the height of the tree. The space requirement for a tree with n nodes is less than 2.5n+(h−1)(2+log₂((n−1)/(h−1))) bits. The access time per node is in O(1). The scheme uses a cumulative-count technique to map the nodes at each level in the tree into sequential memory locations. The mapping requires the nodes to be of uniform size.     

The optimal binary search tree for Andersson's search algorithm

Andersson [1] presented a search algorithm for binary search trees that uses only two-way key comparisons by deferring equality comparisons until the leaves are reached. The use of a different search algorithm means that the optimal tree for the traditional search algorithm, which has been shown to be computable inO(n ²) time by Knuth [3], is not optimal with respect to the different search algorithm. This paper shows that the optimal binary search tree for Andersson's search algorithm can be computed inO(nlogn) time using existing algorithms for the special case of zero successful access frequencies, such as the Hu-Tucker algorithm [2].     

Cache-oblivious index for approximate string matching

This paper revisits the problem of indexing a text for approximate string matching. Specifically, given a text T of length n and a positive integer k, we want to construct an index of T such that for any input pattern P, we can find all its k-error matches in T efficiently. This problem is well-studied in the internal-memory setting. Here, we extend some of these recent results to external-memory solutions, which are also cache-oblivious. Our first index occupies O((nlog^kn)/B) disk pages and finds all k-error matches with O((|P|+occ)/B+log^knloglog_Bn) I/Os, where B denotes the number of words in a disk page. To the best of our knowledge, this index is the first external-memory data structure that does not require Ω(|P|+occ+poly(logn)) I/Os. The second index reduces the space to O((nlogn)/B) disk pages, and the I/O complexity is O((|P|+occ)/B+log^k(k+1)nloglogn).     

Computing rank-width exactly

We prove that the rank-width of an n-vertex graph can be computed exactly in time O(n²n³log²nloglogn). To improve over a trivial O(n³logn)-time algorithm, we develop a general framework for decompositions on which an optimal decomposition can be computed efficiently. This framework may be used for other width parameters, including the branch-width of matroids and the carving-width of graphs.     

The reverse greedy algorithm for the metric k-median problem

The Reverse Greedy algorithm (RGreedy) for the k-median problem works as follows. It starts by placing facilities on all nodes. At each step, it removes a facility to minimize the total distance to the remaining facilities. It stops when k facilities remain. We prove that, if the distance function is metric, then the approximation ratio of RGreedy is between Ω(logn/loglogn) and O(logn).     

Planar tree transformation: Results and counterexample

We consider the problem of planar spanning tree transformation in a two-dimensional plane. Given two planar trees T₁ and T₂ drawn on a set S of n points in general position in the plane, the problem is to transform T₁ into T₂ by a sequence of simple changes called edge-flips or just flips. A flip is an operation by which one edge e of a geometric object is removed and an edge f (f≠e) is inserted such that the resulting object belongs to the same class as the original object. We present two algorithms for planar tree transformations. The first technique is an indirect approach which relies on some ‘canonical’ tree to obtain such transformation results. It is shown that it takes at most 2n−m−s−2 flips (m,s>0) which is an improvement over the result in [D. Avis, K. Fukuda, Reverse search for enumeration, Discrete Applied Mathematics 65 (1996) 21-46]. Second, we present a direct approach which takes at most n−1+k flips (k?0) for such transformation when S in convex position and also show results when the points are in general position. We provide cases where the second technique performs an optimal number of flips. A counterexample is given to show that if |T₁?T₂|=k then they cannot be transformed to one another by k flips.     

Bounds for the Element Distinctness Problem on one-tape Turing machines

We disprove a conjecture of López-Ortiz by showing that the Element Distinctness Problem for n numbers of size O(logn) can be solved in O(n²(logn)^3/2(loglogn)^1/2) steps by a nondeterministic one-tape Turing machine. Further we give a simplified algorithm for solving the problem for shorter numbers in time O(n²logn) on a deterministic one-tape Turing machine and a new proof of the matching lower bound.