Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 46 Issue 2, March 1999

The computational complexity of knot and link problems
Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger
Pages: 185-211
DOI: 10.1145/301970.301971
We consider the problem of deciding whether a polygonal knot in 3-dimensional Euclidean space is unknotted, ie., capable of being continuously deformed without self-intersection so that it lies in a plane. We show that this problem, UNKNOTTING...

Reconstructing a three-dimensional model with arbitrary errors
Bonnie Berger, Jon Kleinberg, Tom Leighton
Pages: 212-235
DOI: 10.1145/301970.301972
A number of current technologies allow for the determination of interatomic distance information in structures such as proteins and RNA. Thus, the reconstruction of a three-dimensional set of points using information about its interpoint...

The string B-tree: a new data structure for string search in external memory and its applications
Paolo Ferragina, Roberto Grossi
Pages: 236-280
DOI: 10.1145/301970.301973
We introduce a new text-indexing data structure, the String B-Tree, that can be seen as a link between some traditional external-memory and string-matching data structures. In a short phrase, it is a combination of B-trees and...

Provably efficient scheduling for languages with fine-grained parallelism
Guy E. Blelloch, Phillip B. Gibbons, Yossi Matias
Pages: 281-321
DOI: 10.1145/301970.301974
Many high-level parallel programming languages allow for fine-grained parallelism. As in the popular work-time framework for parallel algorithm design, programs written in such languages can express the full parallelism in the program without...