Search ACM DL

Search Issue

enter search term and/or author name

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

Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

Pages: 33-47

DOI: 10.1145/1077464.1077468

The

**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, Guy Kortsarz, Wolfgang Slany

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

Stephen Alstrup, Thore Husfeldt, 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, Helmut Prodinger, Jörg M. Thuswaldner

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