ACM Transactions on Algorithms, Volume 3

Volume 3, Number 1, February 2007

Special Issue on SODA 2002

David Eppstein:
Foreword to special issue on SODA 2002.
Electronic Edition (ACM DL) BibTeX
Graham Cormode, S. Muthukrishnan:
The string edit distance matching problem with moves.
Electronic Edition (ACM DL) BibTeX
Aaron Archer, Éva Tardos:
Frugal path mechanisms.
Electronic Edition (ACM DL) BibTeX
Artur Czumaj, Berthold Vöcking:
Tight bounds for worst-case equilibria.
Electronic Edition (ACM DL) BibTeX

Regular Papers

John Hershberger, Subhash Suri, Amit M. Bhosle:
On the difficulty of some shortest path problems.
Electronic Edition (ACM DL) BibTeX
Valentina Ciriani, Paolo Ferragina, Fabrizio Luccio, S. Muthukrishnan:
A data structure for a sequence of string accesses in external memory.
Electronic Edition (ACM DL) BibTeX
Gopal Pandurangan, Eli Upfal:
Entropy-based bounds for online algorithms.
Electronic Edition (ACM DL) BibTeX
Michael Elkin, Guy Kortsarz:
An improved algorithm for radio broadcast.
Electronic Edition (ACM DL) BibTeX
Renato Carmo, Tomás Feder, Yoshiharu Kohayakawa, Eduardo Sany Laber, Rajeev Motwani, Liadan O'Callaghan, Rina Panigrahy, Dilys Thomas:
Querying priced information in databases: The conjunctive case.
Electronic Edition (ACM DL) BibTeX
Randeep Bhatia, Julia Chuzhoy, Ari Freund, Joseph Naor:
Algorithmic aspects of bandwidth trading.
Electronic Edition (ACM DL) BibTeX

Volume 3, Number 2, May 2007

Yevgen Voronenko, Markus Püschel:
Multiplierless multiple constant multiplication.
Electronic Edition (ACM DL) BibTeX
Hua-Huai Chern, Michael Fuchs, Hsien-Kuei Hwang:
Phase changes in random point quadtrees.
Electronic Edition (ACM DL) BibTeX
Erik D. Demaine, John Iacono, Stefan Langerman:
Retroactive data structures.
Electronic Edition (ACM DL) BibTeX
Ryan B. Hayward, Jeremy Spinrad, R. Sritharan:
Improved algorithms for weakly chordal graphs.
Electronic Edition (ACM DL) BibTeX
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch:
Strongly stable matchings in time O(nm) and extension to the hospitals-residents problem.
Electronic Edition (ACM DL) BibTeX
Amitabha Bagchi, Amitabh Chaudhary, David Eppstein, Michael T. Goodrich:
Deterministic sampling and range counting in geometric data streams.
Electronic Edition (ACM DL) BibTeX
Sunil Arya, Theocharis Malamatos, David M. Mount:
A simple entropy-based algorithm for planar point location.
Electronic Edition (ACM DL) BibTeX
Manuel Kauers:
An algorithm for deciding zero equivalence of nested polynomially recurrent sequences.
Electronic Edition (ACM DL) BibTeX
Amihood Amir, Gad M. Landau, Moshe Lewenstein, Dina Sokol:
Dynamic text and static pattern matching.
Electronic Edition (ACM DL) BibTeX
Paolo Ferragina, Giovanni Manzini, Veli Mäkinen, Gonzalo Navarro:
Compressed representations of sequences and full-text indexes.
Electronic Edition (ACM DL) BibTeX
Ho-Leung Chan, Wing-Kai Hon, Tak Wah Lam, Kunihiko Sadakane:
Compressed indexes for dynamic text collections.
Electronic Edition (ACM DL) BibTeX
Joan Boyar, Lene M. Favrholdt:
The relative worst order ratio for online algorithms.
Electronic Edition (ACM DL) BibTeX
Luca Becchetti, Jochen Könemann, Stefano Leonardi, Martin Pál:
Sharing the cost more efficiently: Improved approximation for multicommodity rent-or-buy.
Electronic Edition (ACM DL) BibTeX
David S. Johnson:
The NP-completeness column: Finding needles in haystacks.
Electronic Edition (ACM DL) BibTeX

Volume 3, Number 3, August 2007

Jianxing Feng, Daming Zhu:
Faster algorithms for sorting by transpositions and sorting by block interchanges.
Electronic Edition (ACM DL) BibTeX
Himanshu Gupta, Rephael Wenger:
Constructing pairwise disjoint paths with few links.
Electronic Edition (ACM DL) BibTeX
Chandra Chekuri, Marcelo Mydlarz, F. Bruce Shepherd:
Multicommodity demand flow in a tree and packing integer programs.
Electronic Edition (ACM DL) BibTeX
Amotz Bar-Noy, Richard E. Ladner, Tami Tamir:
Windows scheduling as a restricted version of bin packing.
Electronic Edition (ACM DL) BibTeX
Carmit Hazay, Moshe Lewenstein, Dina Sokol:
Approximate parameterized matching.
Electronic Edition (ACM DL) BibTeX
Magnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki, Hiroki Yanagisawa:
Improved approximation results for the stable marriage problem.
Electronic Edition (ACM DL) BibTeX
Piotr Indyk, Assaf Naor:
Nearest-neighbor-preserving embeddings.
Electronic Edition (ACM DL) BibTeX
Eyal Even-Dar, Alexander Kesselman, Yishay Mansour:
Convergence time to Nash equilibrium in load balancing.
Electronic Edition (ACM DL) BibTeX
Matthew Andrews, Lisa Zhang:
Routing and scheduling in multihop wireless networks with time-varying channels.
Electronic Edition (ACM DL) BibTeX
Moni Naor, Udi Wieder:
Novel architectures for P2P applications: The continuous-discrete approach.
Electronic Edition (ACM DL) BibTeX
Samir Khuller:
Problems column.
Electronic Edition (ACM DL) BibTeX

Volume 3, Number 4, November 2007

Harold N. Gabow, Michael A. Bender, Martin Farach-Colton:
Introduction to SODA 2002 and 2003 special issue.
Electronic Edition (ACM DL) BibTeX
James Aspnes, Gauri Shah:
Skip graphs.
Electronic Edition (ACM DL) BibTeX
Yijie Han:
Optimal parallel selection.
Electronic Edition (ACM DL) BibTeX
Nikhil Bansal, Kedar Dhamdhere:
Minimizing weighted flow time.
Electronic Edition (ACM DL) BibTeX
Jittat Fakcharoenphol, Chris Harrelson, Satish Rao:
The k-traveling repairmen problem.
Electronic Edition (ACM DL) BibTeX
Sandy Irani, Sandeep K. Shukla, Rajesh Gupta:
Algorithms for power savings.
Electronic Edition (ACM DL) BibTeX
Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan:
Guessing secrets efficiently via list decoding.
Electronic Edition (ACM DL) BibTeX
Rajeev Raman, Venkatesh Raman, Srinivasa Rao Satti:
Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets.
Electronic Edition (ACM DL) BibTeX
Svante Janson, Wojciech Szpankowski:
Partial fillup and search time in LC tries.
Electronic Edition (ACM DL) BibTeX
John Hershberger, Matthew Maxel, Subhash Suri:
Finding the k shortest simple paths: A new algorithm and its implementation.
Electronic Edition (ACM DL) BibTeX
Chandra Chekuri, Sanjeev Khanna:
Edge-disjoint paths revisited.
Electronic Edition (ACM DL) BibTeX
Joseph Cheriyan, Mohammad R. Salavatipour:
Packing element-disjoint steiner trees.
Electronic Edition (ACM DL) BibTeX
Michael Krivelevich, Zeev Nutov, Mohammad R. Salavatipour, Jacques Yuster, Raphael Yuster:
Approximation algorithms and hardness results for cycle packing problems.
Electronic Edition (ACM DL) BibTeX
Susanne Albers, Hiroshi Fujiwara:
Energy-efficient algorithms for flow time minimization.
Electronic Edition (ACM DL) BibTeX
Marek Chrobak, Wojciech Jawor, Jiri Sgall, Tomás Tichý:
Improved online algorithms for buffer management in QoS switches.
Electronic Edition (ACM DL) BibTeX
Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Harald Räcke, Tom Leighton:
Oblivious routing on node-capacitated and directed graphs.
Electronic Edition (ACM DL) BibTeX
Vincenzo Auletta, Roberto De Prisco, Paolo Penna, Giuseppe Persiano:
Routing selfish unsplittable traffic.
Electronic Edition (ACM DL) BibTeX