enter search term and/or author name
All pairs shortest paths using bridging sets and rectangular matrix multiplication
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
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
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
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
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...