Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 46 Issue 4, July 1999

Efficient algorithms for inverting evolution
Martin Farach, Sampath Kannan
Pages: 437-449
DOI: 10.1145/320211.320212
Evolution can be mathematically modelled by a stochastic process that operates on the DNA of species. Such models are based on the established theory that the DNA sequences, or genomes, of all extant species have been derived from the genome of...

Primality testing using elliptic curves
Shafi Goldwasser, Joe Kilian
Pages: 450-472
DOI: 10.1145/320211.320213
We present a primality proving algorithm—a probablistic primality test that produces short certificates of primality on prime inputs. We prove that the test runs in expected polynomial time for all but a vanishingly small fraction of the...

On the efficiency of pairing heaps and related data structures
Michael L. Fredman
Pages: 473-501
DOI: 10.1145/320211.320214
The pairing heap is well regarded as an efficient data structure for implementing priority queue operations. It is included in the GNU C++ library. Strikingly simple in design, the pairing heap data structure nonetheless seems difficult to...

Randomized fully dynamic graph algorithms with polylogarithmic time per operation
Monika R. Henzinger, Valerie King
Pages: 502-516
DOI: 10.1145/320211.320215
This paper solves a longstanding open problem in fully dynamic algorithms: We present the first fully dynamic algorithms that maintain connectivity, bipartiteness, and approximate minimum spanning trees in polylogarithmic time per edge insertion...

Mutual search
Harry Buhrman, Matthew Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul Vitányi
Pages: 517-536
DOI: 10.1145/320211.320232
We introduce a search problem called “mutual search” where k agents, arbitrarily distributed over n sites, are required to locate one another by posing queries of the form “Anybody at site...

New results on quantifier elimination over real closed fields and applications to constraint databases
Saugata Basu
Pages: 537-555
DOI: 10.1145/320211.320240
In this paper, we give a new algorithm for quantifier elimination in the first order theory of real closed fields that improves the complexity of the best known algorithm for this problem till now. Unlike previously known algorithms [Basu et al....

Finding circular attributes in attribute grammars
Michael Rodeh, Mooly Sagiv
Pages: 556-ff.
DOI: 10.1145/320211.320243
The problem of finding the circular attributes in an grammar is considered. Two algorithms are proposed: the first is polynomial but yields conservative results while the second is exact but is potentially expontial. It is also shown that...

Corrigendum: editorial: taking stock
Joseph Halpern
Page: 576
DOI: 10.1145/320211.325358