ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 46 Issue 1, Jan. 1999

Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals
Sridhar Hannenhalli, Pavel A. Pevzner
Pages: 1-27
DOI: 10.1145/300515.300516
Genomes frequently evolve by reversals &rgr;(i,j) that transform a gene order &pgr;1 … &pgr;i&pgr;i+1...

Fully dynamic planarity testing with applications
Zvi Galil, Giuseppe F. Italiano, Neil Sarnak
Pages: 28-91
DOI: 10.1145/300515.300517
This paper introduces compressed certificates for planarity, biconnectivity and triconnectivity in planar graphs, and proves many structural properties of certificates in planar graphs. As an application of our compressed certificates, we...

An optimality proof of the LRU-K page replacement algorithm
Elizabeth J. O'Neil, Patrick E. O'Neil, Gerhard Weikum
Pages: 92-112
DOI: 10.1145/300515.300518
This paper analyzes a recently published algorithm for page replacement in hierarchical paged memory systems [O'Neil et al. 1993]. The algorithm is called the LRU-K method, and reduces to the well-known LRU (Least Recently Used)...

Complexity estimates depending on condition and round-off error
Felipe Cucker, Steve Smale
Pages: 113-184
DOI: 10.1145/300515.300519
This paper has two agendas. One is to develop the foundations of round-off in computation. The other is to describe an algorithm for deciding feasibility for polynomial systems of equations and inequalities together with its complexity analysis...