ACM DL

Algorithms (TALG)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Algorithms (TALG), Volume 2 Issue 4, October 2006

Foreword
Alejandro López-Ortiz, J. Ian Munro
Pages: 491-491
DOI: 10.1145/1198513.1198514

Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
David Eppstein
Pages: 492-509
DOI: 10.1145/1198513.1198515
We consider a class of multivariate recurrences frequently arising in the worst-case analysis of Davis-Putnam-style exponential-time backtracking algorithms for NP-hard problems. We describe a technique for proving asymptotic upper bounds on these...

Succinct ordinal trees with level-ancestor queries
Richard F. Geary, Rajeev Raman, Venkatesh Raman
Pages: 510-534
DOI: 10.1145/1198513.1198516
We consider succinct or space-efficient representations of trees that efficiently support a variety of navigation operations. We focus on static ordinal trees, that is, arbitrary static rooted trees where the children of each node are...

Melding priority queues
Ran Mendelson, Robert E. Tarjan, Mikkel Thorup, Uri Zwick
Pages: 535-556
DOI: 10.1145/1198513.1198517
We show that any priority queue data structure that supports insert, delete, and find-min operations in pq(n) amortized time, where n is an upper bound on the number of elements in the priority queue, can be...

Approximate distance oracles for unweighted graphs in expected O(n2) time
Surender Baswana, Sandeep Sen
Pages: 557-577
DOI: 10.1145/1198513.1198518
Let G = (V, E) be an undirected graph on n vertices, and let δ(u, v) denote the distance in G between two vertices u and v. Thorup and Zwick showed that for any positive...

Experimental analysis of dynamic all pairs shortest path algorithms
Camil Demetrescu, Giuseppe F. Italiano
Pages: 578-601
DOI: 10.1145/1198513.1198519
We present the results of an extensive computational study on dynamic algorithms for all pairs shortest path problems. We describe our implementations of the recent dynamic algorithms of King [1999] and of Demetrescu and Italiano [2006], and compare...

Rank-maximal matchings
Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch
Pages: 602-610
DOI: 10.1145/1198513.1198520
Suppose that each member of a set A of applicants ranks a subset of a set P of posts in an order of preference, possibly involving ties. A matching is a set of (applicant, post) pairs such that each applicant and each post...

When indexing equals compression: Experiments with compressing suffix arrays and applications
Luca Foschini, Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter
Pages: 611-639
DOI: 10.1145/1198513.1198521
We report on a new experimental analysis of high-order entropy-compressed suffix arrays, which retains the theoretical performance of previous work and represents an improvement in practice. Our experiments indicate that the resulting text index...

A general approach to online network optimization problems
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph (Seffi) Naor
Pages: 640-660
DOI: 10.1145/1198513.1198522
We study a wide range of online graph and network optimization problems, focusing on problems that arise in the study of connectivity and cuts in graphs. In a general online network design problem, we have a communication network known to the...

Optimally scheduling video-on-demand to minimize delay when sender and receiver bandwidth may differ
William Evans, David Kirkpatrick
Pages: 661-678
DOI: 10.1145/1198513.1198523
We establish tight bounds on the intrinsic cost (either minimizing delay d for fixed sender and receiver bandwidths, or minimizing sender bandwidth for fixed delay and receiver bandwidth) of broadcasting a video of length m over a...

Computing equilibria for a service provider game with (Im)perfect information
Rene Beier, Artur Czumaj, Piotr Krysta, Berthold Vöcking
Pages: 679-706
DOI: 10.1145/1198513.1198524
We study fundamental algorithmic questions concerning the complexity of market equilibria under perfect and imperfect information by means of a basic microeconomic game. Suppose a provider offers a service to a set of potential customers. Each...

Generic quantum Fourier transforms
Cristopher Moore, Daniel Rockmore, Alexander Russell
Pages: 707-723
DOI: 10.1145/1198513.1198525
The quantum Fourier transform (QFT) is a principal ingredient appearing in many efficient quantum algorithms. We present a generic framework for the construction of efficient quantum circuits for the QFT by “quantizing” the highly...