Search ACM DL

Search Issue

enter search term and/or author name

**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(n^{2}) time**

Surender Baswana, Sandeep Sen

Pages: 557-577

DOI: 10.1145/1198513.1198518

Let

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