ACM Transactions on Algorithms, Volume 4

Volume 4, Number 1, March 2008

• Milan Ruzic:
  Uniform deterministic dictionaries.
  
• Gianni Franceschini, Roberto Grossi:
  No sorting? better searching!.
  
• Haim Kaplan, Robert Endre Tarjan:
  Thin heaps, thick heaps.
  
• Jérémy Barbay, Claire Kenyon:
  Alternation and redundancy analysis of the intersection problem.
  
• Seth Pettie, Vijaya Ramachandran:
  Randomized minimum spanning tree algorithms using exponentially fewer random bits.
  
• Liam Roditty:
  A faster and simpler fully dynamic transitive closure.
  
• Harold N. Gabow, Shuxin Nie:
  Finding a long directed cycle.
  
• Adam L. Buchsbaum, Emden R. Gansner, Cecilia Magdalena Procopiuc, Suresh Venkatasubramanian:
  Rectangular layouts and contact graphs.
  
• Lars Arge, Mark de Berg, Herman J. Haverkort, Ke Yi:
  The priority R-tree: A practically efficient and worst-case optimal R-tree.
  
• Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan, Michiel H. M. Smid:
  Approximate distance oracles for geometric spanners.
  
• Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai:
  Improved bounds for scheduling conflicting jobs with minsum criteria.
  
• Rachid Guerraoui, Ron R. Levy, Bastian Pochon, Jim Pugh:
  The collective memory of amnesic processes.
  
• George Karakostas:
  Faster approximation schemes for fractional multicommodity flow problems.
  
• Daniel Lemire, Owen Kaser:
  Hierarchical bin buffering: Online local moments for dynamic external memory arrays.
  
• Elliot Anshelevich, Lisa Zhang:
  Path decomposition under a new cost measure with applications to optical network design.
  

Volume 4, Number 2, May 2008

• Adam L. Buchsbaum:
  Guest editorial.
  
• Daniel K. Blandford, Guy E. Blelloch:
  Compact dictionaries for variable-length keys and data with applications.
  
• Ravi Krishna Kolluri:
  Provably good moving least squares.
  
• Éric Fusy, Gilles Schaeffer, Dominique Poulalhon:
  Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling.
  
• László A. Végh, András A. Benczúr:
  Primal-dual approach for directed vertex connectivity augmentation and generalizations.
  
• Peter Sanders, David Steurer:
  An asymptotic approximation scheme for multigraph edge coloring.
  
• Shuchi Chawla, Anupam Gupta, Harald Räcke:
  Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut.
  
• Julia Chuzhoy, Anupam Gupta, Joseph Naor, Amitabh Sinha:
  On the approximability of some network design problems.
  
• Nicole Immorlica, Mohammad Mahdian, Vahab S. Mirrokni:
  Limitations of cross-monotonic cost-sharing schemes.
  

Volume 4, Number 3, June 2008

• Yefim Dinitz, Shay Solomon:
  Optimality of an algorithm solving the Bottleneck Tower of Hanoi problem.
  
• Laurent Alonso, Edward M. Reingold:
  Determining plurality.
  
• Laurent Alonso, Edward M. Reingold:
  Average-case lower bounds for the plurality problem.
  
• Hsueh-I Lu, Chia-Chi Yeh:
  Balanced parentheses strike back.
  
• Liam Roditty, Mikkel Thorup, Uri Zwick:
  Roundtrip spanners and roundtrip routing in directed graphs.
  
• Qian-Ping Gu, Hisao Tamaki:
  Optimal branch-decomposition of planar graphs in O(n³) Time.
  
• Artur Czumaj, Christian Sohler:
  Testing Euclidean minimum spanning trees in the plane.
  
• Veli Mäkinen, Gonzalo Navarro:
  Dynamic entropy-compressed sequences and full-text indexes.
  
• Dariusz R. Kowalski, Alexander A. Shvartsman:
  Writing-all deterministically and optimally using a nontrivial number of asynchronous processors.
  
• Guy Even, Retsef Levi, Dror Rawitz, Baruch Schieber, Shimon Shahar, Maxim Sviridenko:
  Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs.
  
• Cun-Quan Zhang, Yongbin Ou:
  Clustering, community partition and disjoint spanning trees.
  
• Hung-I Yu, Tzu-Chin Lin, Biing-Feng Wang:
  Improved algorithms for the minmax-regret 1-center and 1-median problems.
  
• Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, Noam Nisan, Mikkel Thorup:
  Compact name-independent routing with minimum stretch.
  
• Kirk Pruhs, Patchrawat Uthaisombut, Gerhard J. Woeginger:
  Getting the best response for your erg.
  

Volume 4, Number 4, August 2008

• Deepak Ajwani, Tobias Friedrich, Ulrich Meyer:
  An O(n^2.75) algorithm for incremental topological ordering.
  
• Louis Ibarra:
  Fully dynamic algorithms for chordal graphs and split graphs.
  
• Amos Korman, David Peleg:
  Dynamic routing schemes for graphs with low local density.
  
• Reuven Cohen, Pierre Fraigniaud, David Ilcinkas, Amos Korman, David Peleg:
  Label-guided graph exploration by a finite automaton.
  
• Akiko Suzuki, Takeshi Tokuyama:
  Dense subgraph problems with output-density conditions.
  
• Amotz Bar-Noy, Panagiotis Cheilaris, Shakhar Smorodinsky:
  Deterministic conflict-free coloring for intervals: From offline to online.
  
• Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Mohammad Ali Safari, Amit Sahai:
  Improved algorithms for optimal embeddings.
  
• Noga Alon, Mihai Badoiu, Erik D. Demaine, Martin Farach-Colton, Mohammad Taghi Hajiaghayi, Anastasios Sidiropoulos:
  Ordinal embeddings of minimum relaxation: General properties, trees, and ultrametrics.
  
• Markus Bläser:
  A new approximation algorithm for the asymmetric TSP with triangle inequality.
  
• Joan Boyar, Paul Medvedev:
  The relative worst order ratio applied to seat reservation.
  
• Tim Nieberg, Johann Hurink, Walter Kern:
  Approximation schemes for wireless networks.
  
• Jens Maßberg, Jens Vygen:
  Approximation algorithms for a facility location problem with service capacities.
  
• Chaitanya Swamy, David B. Shmoys:
  Fault-tolerant facility location.
  
• Dimitris Fotakis, Spyros C. Kontogiannis, Paul G. Spirakis:
  Atomic congestion games among coalitions.
  

Last update Mon May 20 18:28:00 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page