**Recognizing circle graphs in polynomial time**

Csaba P. Gabor, Kenneth J. Supowit, Wen-Lian Hsu

Pages: 435-473

DOI: 10.1145/65950.65951

The main result of this paper is an 0([V] x [E]) time algorithm for deciding whether a given graph is a circle graph, that is, the intersection graph of a set of chords on a circle. The...

**Hierarchical planarity testing algorithms**

Thomas Lengauer

Pages: 474-509

DOI: 10.1145/65950.65952

Using hierarchical definitions, one can describe very large graphs in small space. The blow-up from the length of the hierarchical description to the size of the graph can be as large as exponential. If the efficiency of graph algorithms is...

**A trade-off between space and efficiency for routing tables**

David Peleg, Eli Upfal

Pages: 510-530

DOI: 10.1145/65950.65953

Two conflicting goals play a crucial role in the design of routing schemes for communication networks. A routing scheme should use paths that are as short as possible for routing messages in the network, while keeping the routing information...

**Invariance of complexity measures for networks with unreliable gates**

Nicholas Pippenger

Pages: 531-539

DOI: 10.1145/65950.77248

A new probabilistic failure model for networks of gates is formulated. Although this model has not been used previously, it supports the proofs of both the positive and negative results appearing in the literature. Furthermore, with respect to...

**Efficient implementation of graph algorithms using contraction**

Harold N. Gabow, Zvi Galil, Thomas H. Spencer

Pages: 540-572

DOI: 10.1145/65950.65954

The (component) merging problem is a new graph problem. Versions of this problem appear as bottlenecks in various graph algorithms. A new data structure solves this problem efficiently, and two special cases of...

**Optimum lopsided binary trees**

Sanjiv Kapoor, Edward M. Reingold

Pages: 573-590

DOI: 10.1145/65950.65955

Binary search trees with costs &agr; and &bgr;, respectively, on the left and right edges (lopsided search trees) are considered. The exact shape, minimum worst-case cost, and minimum average cost of lopsided trees of n internal...

**Simple constant-time consensus protocols in realistic failure models**

Benny Chor, Michael Merritt, David B. Shmoys

Pages: 591-614

DOI: 10.1145/65950.65956

Using simple protocols, it is shown how to achieve consensus in constant expected time, within a variety of fail-stop and omission failure models. Significantly, the strongest models considered are completely asynchronous. All of the results are...

**Acyclic fork-join queuing networks**

François Baccelli, William A. Massey, Don Towsley

Pages: 615-642

DOI: 10.1145/65950.65957

In this paper the class of acyclic fork-join queuing networks that arise in various applications, including parallel processing and flexible manufacturing are studied. In such queuing networks, a fork describes the simultaneous creation of...

**Optimal bounds for decision problems on the CRCW PRAM**

Paul Beame, Johan Hastad

Pages: 643-670

DOI: 10.1145/65950.65958

Optimal &OHgr;(log n/log log n) lower bounds on the time for CRCW PRAMS with polynomially bounded numbers of processors or memory cells to compute parity and a number of related problems are proven. A strict...

**New lower bounds for parallel computation**

Ming Li, Yaacov Yesha

Pages: 671-680

DOI: 10.1145/65950.65959

Lower bounds are proven on the parallel-time complexity of several basic functions on the most powerful concurrent-read concurrent-write PRAM with unlimited shared memory and unlimited power of individual processors (denoted by...