Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 49 Issue 3, May 2002

All pairs shortest paths using bridging sets and rectangular matrix multiplication
Uri Zwick
Pages: 289-317
DOI: 10.1145/567112.567114
We present two new algorithms for solving the All Pairs Shortest Paths (APSP) problem for weighted directed graphs. Both algorithms use fast matrix multiplication algorithms.The first algorithm solves the APSP problem for weighted directed graphs in...

Compactly encoding unstructured inputs with differential compression
Miklos Ajtai, Randal Burns, Ronald Fagin, Darrell D. E. Long, Larry Stockmeyer
Pages: 318-367
DOI: 10.1145/567112.567116
The subject of this article is differential compression, the algorithmic task of finding common strings between versions of data and using them to encode one version compactly by describing it as a set of changes from its companion. A main...

On XML integrity constraints in the presence of DTDs
Wenfei Fan, Leonid Libkin
Pages: 368-406
DOI: 10.1145/567112.567117
The article investigates XML document specifications with DTDs and integrity constraints, such as keys and foreign keys. We study the consistency problem of checking whether a given specification is meaningful: that is, whether there exists an XML...

Paradoxes in distributed decisions on optimal load balancing for networks of homogeneous computers
Hisao Kameda, Odile Pourtallier
Pages: 407-433
DOI: 10.1145/567112.567113
In completely symmetric systems that have homogeneous nodes (hosts, computers, or processors) with identical arrival processes, an optimal static load balancing scheme does not involve the forwarding of jobs among nodes. Using an appropriate analytic...

Tight bounds on cache use for stencil operations on rectangular grids
Michael A. Frumkin, Rob F. Van der Wijngaart
Pages: 434-453
DOI: 10.1145/567112.567115
We derive tight bounds on cache misses for evaluation of explicit stencil operators on rectangular grids. Our lower bound is based on the isoperimetric property of the discrete crosspolytope. Our upper bound is based on a good surface-to-volume ratio...