Search ACM DL

Search Issue

enter search term and/or author name

**Uniform deterministic dictionaries**

Milan Ružić

Article No.: 1

DOI: 10.1145/1328911.1328912

We present a new analysis of the well-known family of multiplicative hash functions, and improved deterministic algorithms for selecting “good” hash functions. The main motivation is realization of deterministic dictionaries with fast...

**No sorting? better searching!**

Gianni Franceschini, Roberto Grossi

Article No.: 2

DOI: 10.1145/1328911.1328913

Questions about order versus disorder in systems and models have been fascinating scientists over the years. In computer science, order is intimately related to sorting, commonly meant as the task of arranging keys in increasing or decreasing...

**Thin heaps, thick heaps**

Haim Kaplan, Robert Endre Tarjan

Article No.: 3

DOI: 10.1145/1328911.1328914

The Fibonacci heap was devised to provide an especially efficient implementation of Dijkstra's shortest path algorithm. Although asyptotically efficient, it is not as fast in practice as other heap implementations. Expanding on ideas of...

**Alternation and redundancy analysis of the intersection problem**

Jérémy Barbay, Claire Kenyon

Article No.: 4

DOI: 10.1145/1328911.1328915

The *intersection of sorted arrays* problem has applications in search engines such as Google. Previous work has proposed and compared deterministic algorithms for this problem, in an adaptive analysis based on the encoding size of a...

**Randomized minimum spanning tree algorithms using exponentially fewer random bits**

Seth Pettie, Vijaya Ramachandran

Article No.: 5

DOI: 10.1145/1328911.1328916

For many fundamental problems there exist randomized algorithms that are asymptotically optimal and are superior to the best-known deterministic algorithm. Among these are the minimum spanning tree (MST) problem, the MST sensitivity analysis...

**A faster and simpler fully dynamic transitive closure**

Liam Roditty

Article No.: 6

DOI: 10.1145/1328911.1328917

We obtain a new fully dynamic algorithm for maintaining the transitive closure of a directed graph. Our algorithm maintains the transitive closure matrix in a total running time of *O*(*mn* + (*ins* + *del*) ·...

**Finding a long directed cycle**

Harold N. Gabow, Shuxin Nie

Article No.: 7

DOI: 10.1145/1328911.1328918

Consider a digraph with *n* vertices. For any fixed value *k*, we present linear- and almost-linear-time algorithms to find a cycle of length ≥ *k*, if one exists. We also find a cycle that has length ≥ log *n*/log log...

**Rectangular layouts and contact graphs**

Adam L. Buchsbaum, Emden R. Gansner, Cecilia M. Procopiuc, Suresh Venkatasubramanian

Article No.: 8

DOI: 10.1145/1328911.1328919

Contact graphs of isothetic rectangles unify many concepts from applications including VLSI and architectural design, computational geometry, and GIS. Minimizing the area of their corresponding *rectangular layouts* is a key problem. We study...

**The priority R-tree**: A practically efficient and worst-case optimal R-tree

Lars Arge, Mark De Berg, Herman Haverkort, Ke Yi

Article No.: 9

DOI: 10.1145/1328911.1328920

We present the priority R-tree, or PR-tree, which is the first R-tree variant that always answers a window query using *O*((*N*/*B*)^{1−1/d}+*T*/*B*) I/Os, where *N* is the number of...

**Approximate distance oracles for geometric spanners**

Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan, Michiel Smid

Article No.: 10

DOI: 10.1145/1328911.1328921

Given an arbitrary real constant ϵ > 0, and a geometric graph *G* in *d*-dimensional Euclidean space with *n* points, *O*(*n*) edges, and constant dilation, our main result is a data structure that answers (1...

**Improved bounds for scheduling conflicting jobs with minsum criteria**

Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai

Article No.: 11

DOI: 10.1145/1328911.1328922

We consider a general class of scheduling problems where a set of *conflicting* jobs needs to be scheduled (preemptively or nonpreemptively) on a set of machines so as to minimize the weighted sum of completion times. The conflicts among jobs...

**The collective memory of amnesic processes**

Rachid Guerraoui, Ron R. Levy, Bastian Pochon, Jim Pugh

Article No.: 12

DOI: 10.1145/1328911.1328923

This article considers the problem of robustly emulating a shared atomic memory over a distributed message-passing system where processes can fail by crashing and possibly recover. We revisit the notion of atomicity in the crash-recovery context...

**Faster approximation schemes for fractional multicommodity flow problems**

George Karakostas

Article No.: 13

DOI: 10.1145/1328911.1328924

We present fully polynomial approximation schemes for concurrent multicommodity flow problems that run in time of the minimum possible dependencies on the number of commodities *k*. We show that by modifying the algorithms by Garg and...

**Hierarchical bin buffering**: Online local moments for dynamic external memory arrays

Daniel Lemire, Owen Kaser

Article No.: 14

DOI: 10.1145/1328911.1328925

For a massive I/O array of size *n*, we want to compute the first *N* local moments, for some constant *N*. Our simpler algorithms partition the array into consecutive ranges called bins, and apply not only to local-moment queries,...

**Path decomposition under a new cost measure with applications to optical network design**

Elliot Anshelevich, Lisa Zhang

Article No.: 15

DOI: 10.1145/1328911.1328926

We introduce a problem directly inspired by its application to DWDM (*dense wavelength division multiplexing*) network design. We are given a set of demands to be carried over a network. Our goal is to choose a route for each demand and to...