Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 34 Issue 3, July 1987

An O(n3log n) deterministic and an O(n3) Las Vegs isomorphism test for trivalent graphs
Zvi Galil, Christoph M. Hoffmann, Eugene M. Luks, Claus P. Schnorr, Andreas Weber
Pages: 513-531
DOI: 10.1145/28869.28870
This paper describes an O(n3logn) deterministic algorithm and an O(n3) Las Vegas algorithm for testing whether two...

An efficient algorithm for the “optimal” stable marriage
Robert W. Irving, Paul Leather, Dan Gusfield
Pages: 532-543
DOI: 10.1145/28869.28871
In an instance of size n of the stable marriage problem, each of n men and n women ranks the members of the opposite sex in order of preference. A stable matching is a complete matching of men...

A theory of intersection anomalies in relational database schemes
Catriel Beeri, Michael Kifer
Pages: 544-577
DOI: 10.1145/28869.28872
The desirability of acyclic database schemes is well argued in [8] and [13]. For schemas described by multivalued dependencies, acyclicity means that the dependencies do not split each other's left-hand sides and do not form intersection...

Complete inverted files for efficient text retrieval and analysis
A. Blumer, J. Blumer, D. Haussler, R. McConnell, A. Ehrenfeucht
Pages: 578-595
DOI: 10.1145/28869.28873
Given a finite set of texts S = {w1, … , wk} over some fixed finite alphabet &Sgr;, a complete inverted file for S is an abstract data type that...

Fibonacci heaps and their uses in improved network optimization algorithms
Michael L. Fredman, Robert Endre Tarjan
Pages: 596-615
DOI: 10.1145/28869.28874
In this paper we develop a new data structure for implementing heaps (priority queues). Our structure, Fibonacci heaps (abbreviated F-heaps), extends the binomial queues proposed by Vuillemin and studied further...

New applications of failure functions
D. S. Hirschberg, L. L. Larmore
Pages: 616-625
DOI: 10.1145/28869.28875
Presented are several algorithms whose operations are governed by a principle of failure functions: When searching for an extremal value within a sequence, it suffices to consider only the subsequence of items each of which is the first possible...

Optimal clock synchronization
T. K. Srikanth, Sam Toueg
Pages: 626-645
DOI: 10.1145/28869.28876
We present a simple, efficient, and unified solution to the problems of synchronizing, initializing, and integrating clocks for systems with different types of failures: crash, omission, and arbitrary failures with and without message...

Systems of linear equations with dense univariate polynomial coefficients
Stanley Cabay, Bart Domzy
Pages: 646-660
DOI: 10.1145/28869.28877
An algorithm for computing the power series solution of a system of linear equations with components that are dense univariate polynomials over a field is described and analyzed. A method for converting the power series solution to rational form...

Stochastic catastrophe theory in computer performance modeling
Randolph Nelson
Pages: 661-685
DOI: 10.1145/28869.28878
In this paper catastrophic behavior found in computer systems is investigated. Deterministic Catastrophe theory is introduced first. Then it is shown how the theory can be applied in a stochastic framework, which is useful for understanding...

Infinitesimal perturbation analysis for general discrete event systems
Rajan Suri
Pages: 686-717
DOI: 10.1145/28869.28879
A rigorous extension of the recent perturbation analysis approach to more general discrete event systems is given. First, a general class of systems and performance measures is defined, and some basic reprsentational and linearity properties are...

The existence and density of generalized complexity cores
Ronald V. Book, Ding-Zhu Du
Pages: 718-730
DOI: 10.1145/28869.28880
If C is a class of sets and A is not in C, then an infinite set H is a proper hard core for A with respect to C, if HA...

The equivalence problem for real-time DPDAs
Michio Oyamaguchi
Pages: 731-760
DOI: 10.1145/28869.28881
The equivalence problem for deterministic real-time pushdown automata is shown to be decidable. This result is obtained by showing that Valiant's parallel stacking technique using a replacement function introduced in this paper succeeds for...