**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 H ⊆ A...

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