ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 52 Issue 1, January 2005

Approximate distance oracles
Mikkel Thorup, Uri Zwick
Pages: 1-24
DOI: 10.1145/1044731.1044732
Let G = (V,E) be an undirected weighted graph with |V| = n and |E| = m. Let k ≥ 1 be an integer. We show that G = (V,E) can be preprocessed in...

Determining approximate shortest paths on weighted polyhedral surfaces
L. Aleksandrov, A. Maheshwari, J.-R. Sack
Pages: 25-53
DOI: 10.1145/1044731.1044733
In this article, we present an approximation algorithm for solving the single source shortest paths problem on weighted polyhedral surfaces. We consider a polyhedral surface P as consisting of n triangular faces, where each face has an...

Aggregate operators in probabilistic databases
Robert Ross, V. S. Subrahmanian, John Grant
Pages: 54-101
DOI: 10.1145/1044731.1044734
Though extensions to the relational data model have been proposed in order to handle probabilistic information, there has been very little work to date on handling aggregate operators in such databases. In this article, we present a very general...

Analyzing security protocols with secrecy types and logic programs
Martín Abadi, Bruno Blanchet
Pages: 102-146
DOI: 10.1145/1044731.1044735
We study and further develop two language-based techniques for analyzing security protocols. One is based on a typed process calculus; the other, on untyped logic programs. Both focus on secrecy properties. We contribute to these two techniques, in...