Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 38 Issue 1, Jan. 1991

A random polynomial-time algorithm for approximating the volume of convex bodies
Martin Dyer, Alan Frieze, Ravi Kannan
Pages: 1-17
DOI: 10.1145/102782.102783
A randomized polynomial-time algorithm for approximating the volume of a convex body K in n-dimensional Euclidean space is presented. The proof of correctness of the algorithm relies on recent theory of rapidly...

The weighted region problem: finding shortest paths through a weighted planar subdivision
Joseph S. B. Mitchell, Christos H. Papadimitriou
Pages: 18-73
DOI: 10.1145/102782.102784
The problem of determining shortest paths through a weighted planar polygonal subdivision with n vertices is considered. Distances are measured according to a weighted Euclidean metric: The length of a path is defined to be the...

A fast planar partition algorithm, II
Kentan Mulmuley
Pages: 74-103
DOI: 10.1145/102782.102785
Randomized, optimal algorithms to find a partition of the plane induced by a set of algebraic segments of a bounded degree, and a set of linear chains of a bounded degree, are given. This paper also provides a new technique for clipping, called...

Optimal sample cost residues for differential database batch query problems
Dan E. Willard
Pages: 104-119
DOI: 10.1145/102782.102786
In many computing applications, there are several equivalent algorithms capable of performing a particular task, and no one is the most efficient under all statistical distributions of the data. In such contexts, a good heuristic is to take a...

Evaluation of queries in independent database schemes
Yehoshua Sagiv
Pages: 120-161
DOI: 10.1145/102782.102787
A simple characterization of independent database schemes is proved. An algorithm is given for translating a tableau T, posed as a query on a representative instance, to a union of tableaux that is equivalent to...

Planar graph decomposition and all pairs shortest paths
Greg N. Frederickson
Pages: 162-204
DOI: 10.1145/102782.102788
An algorithm is presented for generating a succinct encoding of all pairs shortest path information in a directed planar graph G with real-valued edge costs but no negative cycles. The algorithm runs in...

Extended Horn sets in propositional logic
V. Chandru, J. N. Hooker
Pages: 205-221
DOI: 10.1145/102782.102789
The class of Horn clause sets in propositional logic is extended to a larger class for which the satisfiability problem can still be solved by unit resolution in linear time. It is shown that to every arborescence there corresponds a family of...

Upper and lower bounds on switching energy in VLSI
Gloria Kissin
Pages: 222-254
DOI: 10.1145/102782.102790
A technology-independent framework is established for measuring the switching energy consumed by very large scale integrated (VLSI) circuits. Techniques are developed for analyzing functional energy...