Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 1 Issue 1, July 2005

Editor's foreword
Harold N. Gabow
Pages: 1-1
DOI: 10.1145/1077464.1077465

Fast sparse matrix multiplication
Raphael Yuster, Uri Zwick
Pages: 2-13
DOI: 10.1145/1077464.1077466
Let A and B two n×n matrices over a ring R (e.g., the reals or the integers) each containing at most m nonzero elements. We present a new algorithm that multiplies A and B using...

A maiden analysis of longest wait first
Jeff Edmonds, Kirk Pruhs
Pages: 14-32
DOI: 10.1145/1077464.1077467
We consider server scheduling strategies to minimize average flow time in a multicast pull system where data items have uniform size. The algorithm Longest Wait First (LWF) always services the page where the aggregate waiting times of the outstanding...

Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs
Dimitrios M. Thilikos, Fedor V. Fomin, Erik D. Demaine, Mohammadtaghi Hajiaghayi
Pages: 33-47
DOI: 10.1145/1077464.1077468
The (k, r)-center problem asks whether an input graph G has ≤k vertices (called centers) such that every vertex of G is within distance ≤r from some center. In this article, we prove that...

Pricing multicasting in more flexible network models
Micah Adler, Dan Rubenstein
Pages: 48-73
DOI: 10.1145/1077464.1077469
The problem of designing efficient algorithms for sharing the cost of multicasting has recently received considerable attention. In this article, we examine the effect on the complexity of pricing when two flexibility-enhancing mechanisms are...

On network design problems: fixed cost flows and the covering steiner problem
Guy Even, Wolfgang Slany, Guy Kortsarz
Pages: 74-101
DOI: 10.1145/1077464.1077470
Network design problems, such as generalizations of the Steiner Tree Problem, can be cast as edge-cost-flow problems. An edge-cost flow problem is a min-cost flow problem in which the cost of the flow equals the sum of the costs of the edges carrying...

Black box for constant-time insertion in priority queues (note)
Thore Husfeldt, Stephen Alstrup, Theis Rauhe, Mikkel Thorup
Pages: 102-106
DOI: 10.1145/1077464.1077471
We present a simple black box that takes a priority queue Q which supports find-min, insert, and delete in x-time at most t. Here x-time may be worst-case, expected, or amortized. The black-box transforms Q into a priority queue...

A linear-time approximation algorithm for weighted matchings in graphs
Doratha E. Drake Vinkemeier, Stefan Hougardy
Pages: 107-122
DOI: 10.1145/1077464.1077472
Approximation algorithms have so far mainly been studied for problems that are not known to have polynomial time algorithms for solving them exactly. Here we propose an approximation algorithm for the weighted matching problem in graphs which can be...

Analysis of linear combination algorithms in cryptography
Peter J. Grabner, Clemens Heuberger, Jörg M. Thuswaldner, Helmut Prodinger
Pages: 123-142
DOI: 10.1145/1077464.1077473
Several cryptosystems rely on fast calculations of linear combinations in groups. One way to achieve this is to use joint signed binary digit expansions of small “weight.” We study two algorithms, one based on nonadjacent forms of the...

On a generalization of the stable roommates problem
Katarína Cechlárová, Tamás Fleiner
Pages: 143-156
DOI: 10.1145/1077464.1077474
We consider two generalizations of the stable roommates problem: a) we allow parallel edges in the underlying graph, and b) we study a problem with multiple partners. We reduce both problems to the classical stable roommates problem and describe an...

Problems column
Samir Khuller
Pages: 157-159
DOI: 10.1145/1077464.1077475

The NP-completeness column
David S. Johnson
Pages: 160-176
DOI: 10.1145/1077464.1077476
This is the 24th 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...