Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 48 Issue 1, Jan. 2001

Dynamic planar convex hull operations in near-logarithmic amortized time
Timothy M. Chan
Pages: 1-12
DOI: 10.1145/363647.363652
We give a data structure that allows arbitrary insertions and deletions on a planar point set P and supports basic queries on the convex hull of P, such as membership and tangent-finding. Updates take...

Adversarial queuing theory
Allan Borodin, Jon Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson
Pages: 13-38
DOI: 10.1145/363647.363659
We consider packet routing when packets are injected continuously into a network. We develop an adversarial theory of queuing aimed at addressing some of the restrictions inherent in probabilistic analysis and queuing theory based on...

Universal-stability results and performance bounds for greedy contention-resolution protocols
Matthew Andrews, Baruch Awerbuch, Antonio Fernández, Tom Leighton, Zhiyong Liu, Jon Kleinberg
Pages: 39-69
DOI: 10.1145/363647.363677
In this paper, we analyze the behavior of packet-switched communication networks in which packets arrive dynamically at the nodes and are routed in discrete time steps across the edges. We focus on a basic adversarial model of packet arrival and...

Automated complexity analysis based on ordered resolution
David Basin, Harald Ganzinger
Pages: 70-109
DOI: 10.1145/363647.363681
We define order locality to be a property of clauses relative to a term ordering. This property generalizes the subformula property for proofs where the terms appearing in proofs can be bounded, under the given ordering, by terms appearing in...

Lattice computers for approximating Euclidean space
John Case, Dayanand S. Rajan, Anil M. Shende
Pages: 110-144
DOI: 10.1145/363647.363688
In the context of mesh-like, parallel processing computers for (i) approximating continuous space and (ii) analog simulation of the motion of objects and waves in continuous space, the present paper is concerned with...

a counterexample to W. Bibel's and E. Eder's strong completeness result for connection graph resolution
Jörg H. Siekmann, Graham Wrightson
Pages: 145-147
DOI: 10.1145/363647.363697