Efficient reduction for path problems on circular-arc graphs

An efficient reduction process for path problems on circular-arc graphs is introduced. For the parity path problem, this reduction gives anO(n+m) algorithm for proper circular-arc graphs, and anO(n+m) algorithm for general circular-arc graphs. This reduction also gives anO(n+m) algorithm for the two path problem on circular-arc graphs.     

The most vital edges with respect to the number of spanning trees in two-terminal series-parallel graphs

A setE ofk edges in a multigraphG=(V,E) is said to be ak most vital edge set (k-MVE set) if these edges being removed fromG, the resultant graphG=(V,E –E) has minimum number of spanning trees. The problem of finding ak-MVE set for two-terminal series-parallel graphs is considered in this paper. We present anO (|E|) time algorithm for the casek=1, and anO(|V| ^k +|E|) time algorithm for arbitraryk.     

Quotient tree partitioning of undirected graphs

The partitioning of the vertices of an undirected graph, in a way that makes its quotient graph a tree, mirrors a way of permuting a square symmetric matrix to allow its factoring with little fill-in. We analyze the complexity of finding the best partitioning and show that it is NP-complete. We also give a new and simpler implementation of an algorithm that finds a maximal quotient tree.     

A linear time and space algorithm for finding isomorphic subtrees of a binary tree

This paper shows that it is possible to find all isomorphic subtrees of a binary tree in linear time and space.     

Improved bounds for the expected behaviour of AVL trees

In this paper we improve previous bounds on expected measures of AVL trees by using fringe analysis. A new way of handling larger tree collections that are not closed is presented. An inherent difficulty posed by the transformations necessary to keep the AVL tree balanced makes its analysis difficult when using fringe analysis methods. We derive a technique to cope with this difficulty obtaining the exact solution for fringe parameters even when unknown probabilities are involved. We show that the probability of a rotation in an insertion is between 0.37 and 0.73 (and seems to be less than 0.56), that the fraction of balanced nodes is between 0.56 and 0.78, and that the expected number of comparisons in a search seems to be at most 12% more than in the complete balanced tree.The work of the first author was also supported by the Institute for Computer Research of the University of Waterloo, the second author by a Natural Sciences and Engineering Research Council of Canada Grant No. A-3353, and the third by a Brazilian Coordenação do Aperfeiçoamento de Pessoal de Nível Superior Contract No. 4799/77 and by the University of Waterloo.     

A note on the height of thekth element in a heap

De Graaf and Kosters have studied the expected height of thekth element in a heap. They conjecture that, for largek, this is asymptotic to log₂ k + 0.72 .... We show that the height of thekth element is related to the depth of insertion in a digital search tree, and use this relation to prove their conjecture.This research was supported by grant FONDECYT (Chile) 91-1252.     

Partitioning multi-edge graphs

We introduce a new kind of graph called multi-edge graph which arises in many applications such as finite state Markov chains and broadcasting communication networks. A cluster in such a graph is a set of nodes such that for any ordered pair of nodes, there is a path of multi-edges from one to the other such that these edges remain within the same set. We give two algorithms to partition a multi-edge graph into maximal clusters. Both these algorithms are based on the depth-first search algorithm to find strongly connected components of the directed graph. We also discuss some applications of clustering in multi-edge graphs.     

Left distance binary tree representations

We present a new scheme for representing binary trees. The scheme is based on rotations as a previous scheme of Zerling. In our method the items of a representation have a natural geometric interpretation, and the algorithms related to the method are simple. We give an algorithm for enumerating all the representations for trees onn nodes, and an algorithm for building the tree corresponding to a given representation.This work was supported by the Academy of Finland.     

Expected heights in heaps

In this paper several recurrences and formulas are presented leading to upper and lower bounds, both logarithmic, for the expected height of a node in a heap. These bounds are of interest for algorithms that select thekth smallest element in a heap.     

A generalized hypergreedy algorithm for weighted perfect matching

We give a generalization of the hypergreedy algorithm for minimum weight perfect matching on a complete edge weighted graph whose weights satisfy the triangle inequality. With a modified version of this algorithm we obtain a logn-approximate perfect matching heuristic for points in the Euclidean plane, inO(n log² n) time.This research was supported in part by the DIMACS Grant No. NSF-STC88-09648.This research was supported in part by the NSF under Grant No. CCR 88-07518.     

Page usage in a quadtree index

This paper provides a characterization of the storage needs of a quadtree when used as an index to access large volumes of 2-dimensional data. It is shown that the page occupancy for data in random order approaches 33%. A precise mathematical analysis that involves a modicum of hypergeometric functions and dilogarithms, together with some computer algebra is presented.A brief survey of the analysis of storage usage in tree structures is included. The 33% ratio for quadtrees is to be compared to the figures for binary search trees (50%), tries (69%), and quadtries (46%).The research of this author was done while visiting INRIA, Rocquencourt, France under support from the Ministry of Education of Japanese Government.Work of this author was supported in part by the Basic Research Action of the E.C. under contract No. 3075 (Project ALCOM).     

Average search and update costs in skip lists

Skip lists, introduced by Pugh, provide an alternative to search trees, although a precise analysis of their behaviour had been elusive. The exact value of the expected cost for the search of themth element in a skip list ofn elements is derived first in terms of previously studied functions, and secondly as an asymptotic expression. The latter suggests that Pugh's upper bound of the expected search cost is fairly tight for the interesting cases. Assuming a uniform query distribution, the exact and an asymptotic value of the average (over allm) expected search cost in a skip list ofn elements is also derived. Finally, all insert and delete costs are obtained.This research was supported in part by the Natural Science and Engineering Research Council of Canada under grant No. A-8237, the Information Technology Research Centre of Ontario, and FON-DECYT (Chile) under grant 91-1252.     

Searchability in merging and implicit data structures

We introduce the notion ofsearchability as a property of an in place merging algorithm. We show that a pair of sorted arrays can be merged in place in linear time, so that a search can be performed in logarithmic time at any point during the merging process. We apply this method to devise an implicit data structure which can support searches inO(log² n) time in the worst case, andO(logn) on the average, and insertions inO(logn) time, in the worst case.This research was partly supported by NSERC under grant A8237 and presented in preliminary form at the 10th International Colloquium on Automata, Languages and Programming.On leave from the University of Chile.     

Finding squares and rectangles in sets of points

A number of problems concerning sets of points in the plane are studied, e.g. establishing whether it contains a subset of size 4, which are the vertices of a square or rectangle. Both the problems of finding axis-parallel squares and rectangles, and arbitrarily oriented squares and rectangles are studied. Efficient algorithms are obtained for all of them. Furthermore, we investigate the generalizations tod-dimensional space, where the problem is to find hyperrectangles and hypercubes. Also, upper and lower bounds are given for combinatorial problems on the maxium number of subsets of size 4, of which the points are the vertices of a square or rectangle. Then we state an equivalence between the problem of finding rectangles, and the problem of findingK _{2, 2} subgraphs in bipartite graphs. Thus we immediately have an efficient algorithm for this graph problem.This work was partially supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). Work of the second author was also supported by the Dutch Organisation for Scientific Research (N.W.O.).     

Canonical representations of partial 2- and 3-trees

We give algorithms constructing canonical representations of partial 2-trees (series parallel graphs) and partial 3-trees. The algorithms can be implemented in log-linear space, or in linear time using quadratic space.Supported in part by a grant from the Swedish Natural Science Research Council.Research supported in part by the Office of Naval Research Contract N00014-86-K-0419.     

On Shellsort and the frobenius problem

A boundO(N ^1+1/k ) for the running time of Shellsort, withO(logN) passes, is proved very simply by application of a Frobenius basis withk elements.     

A dual approach to detect polyhedral intersections in arbitrary dimensions

This paper presents a dual approach to detect intersections of hyperplanes and convex polyhedra in arbitrary dimensions. Ind dimensions, the time complexities of the dual algorithms areO(2 ^d logn) for the hyperplane-polyhedron intersection problem, andO((2d) ^d–1 log ^d–1 n) for the polyhedron- polyhedron intersection problem. These results are the first of their kind ford > 3. In two dimensions, these time bounds are achieved with linear space and preprocessing. In three dimensions, the hyperplane-polyhedron intersection problem is also solved with linear space and preprocessing; quadratic space and preprocessing, however, is required for the polyhedron-polyhedron intersection problem. For generald, the dual algorithms require space and preprocessing. All of these results readily extend to unbounded polyhedra.This is an extended and revised version of a paper presented at the 25th Annual Allerton Conference on Communication, Control, and Computing (October 1987). Our work was sponsored by the U.S. Army Research Office (research contract DAAG29-85-0223) and, in the case of the first author, by graduate fellowships from the IBM corporation and the German National Scholarship Foundation.     

Optimal parallel quicksort on EREW PRAM

In this paper, we present parallel quicksort algorithms running inO((n/p+logp) logn) expected time andO((n/p+logp+log logn) logn) deterministic time respectively, and both withO(n) space by usingp processors on EREW PRAM. Whenp=O(n/logn), the cost is optimal, in terms of the product of time and number of processors. These algorithms can be used to obtain parallel algorithms for constructing balanced binary search trees without using sorting algorithms. One of our quicksort algorithms leads to a parallel quickhull algorithm on EREW PRAM.The work of this author was partially supported by a fellowship from the College of Science, Old Dominion University, Norfolk, VA 23529, USA.     

On top-down splaying

The splay tree is a self-adjusting binary search tree which has a good amortized performance. This paper studies some properties of top-down splay trees. Different ways to charge for the primitive operations of top-down splaying are discussed. We also give some empirical results concerning the behaviour of different top-down restructuring algorithms.This work was supported by the Academy of Finland.