ACM Transactions on Algorithms, Volume 3

Volume 3, Number 1, February 2007

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

• John Hershberger, Subhash Suri, Amit M. Bhosle:
  On the difficulty of some shortest path problems.
  
• Valentina Ciriani, Paolo Ferragina, Fabrizio Luccio, S. Muthukrishnan:
  A data structure for a sequence of string accesses in external memory.
  
• Gopal Pandurangan, Eli Upfal:
  Entropy-based bounds for online algorithms.
  
• Michael Elkin, Guy Kortsarz:
  An improved algorithm for radio broadcast.
  
• 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.
  
• Randeep Bhatia, Julia Chuzhoy, Ari Freund, Joseph Naor:
  Algorithmic aspects of bandwidth trading.
  

Volume 3, Number 2, May 2007

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

Volume 3, Number 3, August 2007

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

Volume 3, Number 4, November 2007

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