Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 3 Issue 2, May 2007

Multiplierless multiple constant multiplication
Yevgen Voronenko, Markus Püschel
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, Michael Fuchs, Hsien-Kuei Hwang
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
Erik D. Demaine, John Iacono, 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
Ryan B. Hayward, Jeremy P. Spinrad, 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(mn2) to O(m2) and the space...

Strongly stable matchings in time O(nm) and extension to the hospitals-residents problem
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch
Article No.: 15
DOI: 10.1145/1240233.1240238

An instance of the stable marriage problem is an undirected bipartite graph G = (XW, 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
Amitabha Bagchi, Amitabh Chaudhary, David Eppstein, Michael T. Goodrich
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
Amihood Amir, Gad M. Landau, Moshe Lewenstein, Dina Sokol
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
Paolo Ferragina, Giovanni Manzini, Veli Mäkinen, Gonzalo Navarro
Article No.: 20
DOI: 10.1145/1240233.1240243

Given a sequence S = s1s2sn of integers smaller than r = O(polylog(n)), we show how S can be represented using...

Compressed indexes for dynamic text collections
Ho-Leung Chan, Wing-Kai Hon, Tak-Wah Lam, Kunihiko Sadakane
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
L. Becchetti, J. Könemann, S. Leonardi, M. Páal
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 (s1, t1), …, (sk,...

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