Search ACM DL

Search Issue

enter search term and/or author name

**Multiplierless multiple constant multiplication**

Markus Püschel, Yevgen Voronenko

Article No.: 11

DOI: 10.1145/1240233.1240234

A variable can be multiplied by a given set of fixed-point constants using a multiplier block that consists exclusively of additions, subtractions, and shifts. The generation of a multiplier block from the set of constants is known as the multiple...

**Phase changes in random point quadtrees**

Hua-Huai Chern, Hsien-Kuei Hwang, Michael Fuchs

Article No.: 12

DOI: 10.1145/1240233.1240235

We show that a wide class of linear cost measures (such as the number of leaves) in random *d*-dimensional point quadtrees undergo a change in limit laws: If the dimension *d* = 1, …, 8, then the limit law is normal; if...

**Retroactive data structures**

John Iacono, Erik D. Demaine, Stefan Langerman

Article No.: 13

DOI: 10.1145/1240233.1240236

We introduce a new data structuring paradigm in which operations can be performed on a data structure not only in the present, but also in the past. In this new paradigm, called *retroactive data structures*, the historical sequence of...

**Improved algorithms for weakly chordal graphs**

Jeremy P. Spinrad, Ryan B. Hayward, R. Sritharan

Article No.: 14

DOI: 10.1145/1240233.1240237

We use a new structural theorem on the presence of two-pairs in weakly chordal graphs to develop improved algorithms. For the recognition problem, we reduce the time complexity from O(*mn*^{2}) to O(*m*^{2}) and the space...

**Strongly stable matchings in time O(nm) and extension to the hospitals-residents problem**

Katarzyna E. Paluch, Dimitrios Michail, Telikepalli Kavitha, Kurt Mehlhorn

Article No.: 15

DOI: 10.1145/1240233.1240238

An instance of the stable marriage problem is an undirected bipartite graph *G* = (*X* ∪ *W*, *E*) with linearly ordered adjacency lists with ties allowed in the ordering. A matching *M* is a set of edges, no...

**Deterministic sampling and range counting in geometric data streams**

Amitabh Chaudhary, Michael T. Goodrich, Amitabha Bagchi, David Eppstein

Article No.: 16

DOI: 10.1145/1240233.1240239

We present memory-efficient deterministic algorithms for constructing ε-nets and ε-approximations of streams of geometric data. Unlike probabilistic approaches, these deterministic samples provide guaranteed bounds on their approximation...

**A simple entropy-based algorithm for planar point location**

Sunil Arya, Theocharis Malamatos, David M. Mount

Article No.: 17

DOI: 10.1145/1240233.1240240

Given a planar polygonal subdivision *S*, point location involves preprocessing this subdivision into a data structure so that given any query point *q*, the cell of the subdivision containing *q* can be determined efficiently....

**An algorithm for deciding zero equivalence of nested polynomially recurrent sequences**

Manuel Kauers

Article No.: 18

DOI: 10.1145/1240233.1240241

We introduce the class of nested polynomially recurrent sequences which includes a large number of sequences that are of combinatorial interest. We present an algorithm for deciding zero equivalence of these sequences, thereby providing a new...

**Dynamic text and static pattern matching**

Gad M. Landau, Amihood Amir, Dina Sokol, Moshe Lewenstein

Article No.: 19

DOI: 10.1145/1240233.1240242

In this article, we address a new version of dynamic pattern matching. The *dynamic text and static pattern matching problem* is the problem of finding a static pattern in a text that is continuously being updated. The goal is to report all...

**Compressed representations of sequences and full-text indexes**

Veli Mäkinen, Gonzalo Navarro, Paolo Ferragina, Giovanni Manzini

Article No.: 20

DOI: 10.1145/1240233.1240243

Given a sequence *S* = *s*_{1}*s*_{2}…*s*_{n} of integers smaller than *r* = *O*(polylog(*n*)), we show how *S* can be represented using...

**Compressed indexes for dynamic text collections**

Tak-Wah Lam, Kunihiko Sadakane, Wing-Kai Hon, Ho-Leung Chan

Article No.: 21

DOI: 10.1145/1240233.1240244

Let *T* be a string with *n* characters over an alphabet of constant size. A recent breakthrough on compressed indexing allows us to build an index for *T* in optimal space (i.e., *O*(*n*) bits), while supporting very...

**The relative worst order ratio for online algorithms**

Joan Boyar, Lene M. Favrholdt

Article No.: 22

DOI: 10.1145/1240233.1240245

We define a new measure for the quality of online algorithms, the *relative worst order ratio*, using ideas from the max/max ratio [Ben-David and Borodin 1994] and from the random order ratio [Kenyon 1996]. The new ratio is used to compare...

**Sharing the cost more efficiently**: Improved approximation for multicommodity rent-or-buy

M. Páal, L. Becchetti, J. Könemann, S. Leonardi

Article No.: 23

DOI: 10.1145/1240233.1240246

In the *multicommodity rent-or-buy* (MROB) network design problems, we are given a network together with a set of *k* terminal pairs (*s*_{1}, *t*_{1}), …, (*s*_{k},...

**The NP-completeness column**: Finding needles in haystacks

David S. Johnson

Article No.: 24

DOI: 10.1145/1240233.1240247

This is the 26th edition of a column that covers new developments in the theory of NP-completeness. The presentation is modeled on that which M. R. Garey and I used in our book “Computers and Intractability: A Guide to the Theory of...