Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 4 Issue 1, March 2008

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...