Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 36 Issue 3, July 1989

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...