Volume 6, Number 1, December 2009

• 
  Irene Finocchi, Fabrizio Grandoni, Giuseppe F. Italiano: Resilient dictionaries.
• 
  Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann: An optimal decomposition algorithm for tree edit distance.
• 
  Philip Bille, Rolf Fagerberg, Inge Li Gørtz: Improved approximate string matching and regular expression matching on Ziv-Lempel compressed texts.
• 
  Amalia Duch, Conrado Martínez: Updating relaxed K-d trees.
• 
  Zeev Nutov: Approximating connectivity augmentation problems.
• 
  Camil Demetrescu, Irene Finocchi, Andrea Ribichini: Trading off space for passes in graph streaming problems.
• 
  Seth Pettie: Low distortion spanners.
• 
  Kurt Mehlhorn, Dimitrios Michail: Minimum cycle bases: Faster and simpler.
• 
  Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Ioan Todinca: Exponential time algorithms for the minimum dominating set problem on some graph classes.
• 
  Ho-Leung Chan, Joseph Wun-Tat Chan, Tak Wah Lam, Lap-Kei Lee, Kin-Sum Mak, Prudence W. H. Wong: Optimizing throughput and energy in online deadline scheduling.
• 
  Noga Alon, Yossi Azar, Shai Gutner: Admission control to minimize rejections and online set cover with repetitions.
• 
  David Hay, Gabriel Scalosub: Jitter regulation for multiple streams.
• 
  Luca Becchetti, Alberto Marchetti-Spaccamela, Andrea Vitaletti, Peter Korteweg, Martin Skutella, Leen Stougie: Latency-constrained aggregation in sensor networks.
• 
  Rami Cohen, Dror Rawitz, Danny Raz: Time-dependent multi-scheduling of multicast.
• 
  Iftah Gamzu, Danny Segev: Improved online algorithms for the sorting buffer problem on line metrics.
• 
  Konstantin Andreev, Charles Garrod, Daniel Golovin, Bruce M. Maggs, Adam Meyerson: Simultaneous source location.
• 
  Wolfgang W. Bein, Mordecai J. Golin, Lawrence L. Larmore, Yan Zhang: The Knuth-Yao quadrangle-inequality speedup is a consequence of total monotonicity.
• 
  Refael Hassin, Asaf Levin, Maxim Sviridenko: Approximating the minimum quadratic assignment problems.
• 
  Gorjan Alagic, Cristopher Moore, Alexander Russell: Quantum algorithms for Simon's problem over nonabelian groups.
• 
  László Babai, Pedro F. Felzenszwalb: Computing rank-convolutions with a mask.
• 
  F. Thomas Bruss, Guy Louchard, Mark Daniel Ward: Inverse auctions: Injecting unique minima into random sets.

Volume 6, Number 2, March 2010

• 
  Susanne Albers: Editorial Note.
• 
  Claire Mathieu: Foreword to special issue SODA 2009.
• 
  Sergio Cabello: Finding shortest contractible and shortest separating cycles in embedded graphs.
• 
  James Aspnes, Keren Censor: Approximate shared-memory counting despite a strong adversary.
• 
  Timothy M. Chan: Comparison-based time-space lower bounds for selection.
• 
  Ashish Goel, Michael Kapralov, Sanjeev Khanna: Perfect matchings via uniform sampling in regular bipartite graphs.
• 
  Benjamin Aminof, Orna Kupferman, Robby Lampert: Reasoning about online algorithms with weighted automata.
• 
  Dániel Marx: Approximating fractional hypertree width.
• 
  Philip N. Klein, Shay Mozes, Oren Weimann: Shortest paths in directed planar graphs with negative lengths: A linear-space O(n log² n)-time algorithm.
• 
  Konstantinos Panagiotou, Angelika Steger: Maximal biconnected subgraphs of random planar graphs.
• 
  Stéphan Thomassé: A 4k² kernel for feedback vertex set.
• 
  Omid Madani, Mikkel Thorup, Uri Zwick: Discounted deterministic Markov decision processes and discounted all-pairs shortest paths.
• 
  Alon Shalita, Uri Zwick: Efficient algorithms for the 2-gathering problem.
• 
  Nikhil Bansal, Ning Chen, Neva Cherniavsky, Atri Rudra, Baruch Schieber, Maxim Sviridenko: Dynamic pricing for impatient bidders.
• 
  Yossi Azar, Iftah Gamzu, Shai Gutner: Truthful unsplittable flow for large capacity networks.
• 
  Zoya Svitkina, Éva Tardos: Facility location with hierarchical facility costs.
• 
  George Christodoulou, Elias Koutsoupias, Annamária Kovács: Mechanism design for fractional scheduling on unrelated machines.
• 
  Amos Korman: Labeling schemes for vertex connectivity.
• 
  Ayelet Butman, Danny Hermelin, Moshe Lewenstein, Dror Rawitz: Optimization problems in multiple-interval graphs.
• 
  Anupam Gupta, Mohammad Taghi Hajiaghayi, Viswanath Nagarajan, R. Ravi: Dial a Ride from k-forest.
• 
  Bruce A. Bobier, Joe Sawada: A fast algorithm to generate open meandric systems and meanders.
• 
  Funda Ergün, S. Muthukrishnan, Süleyman Cenk Sahinalp: Periodicity testing with sublinear samples and space.

Volume 6, Number 3, June 2010

• 
  Virginia Vassilevska, Ryan Williams, Raphael Yuster: Finding heaviest H-subgraphs in real weighted graphs, with applications.
• 
  Frank Ruskey, Aaron Williams: An explicit universal cycle for the (n-1)-permutations of an n-set.
• 
  Matthew Drescher, Adrian Vetta: An approximation algorithm for the maximum leaf spanning arborescence problem.
• 
  Joseph Naor, Roy Schwartz: The directed circular arrangement problem.
• 
  Yossi Azar, Shay Kutten, Boaz Patt-Shamir: Distributed error confinement.
• 
  Gagan Aggarwal, Rina Panigrahy, Tomás Feder, Dilys Thomas, Krishnaram Kenthapadi, Samir Khuller, An Zhu: Achieving anonymity via clustering.
• 
  Eyal Gordon, Adi Rosén: Competitive weighted throughput analysis of greedy protocols on DAGs.
• 
  Amit Chakrabarti, Graham Cormode, Andrew McGregor: A near-optimal algorithm for estimating the entropy of a stream.
• 
  Shahar Fattal, Dana Ron: Approximating the distance to monotonicity in high dimensions.
• 
  Conrado Martínez, Daniel Panario, Alfredo Viola: Adaptive sampling strategies for quickselects.
• 
  Noga Alon, Shai Gutner: Balanced families of perfect hash functions and their applications.
• 
  Don Coppersmith, Lisa Fleischer, Atri Rudra: Ordering by weighted number of wins gives a good ranking for weighted tournaments.
• 
  Arturo Gonzalez-Gutierrez, Teofilo F. Gonzalez: Approximating corridors and tours via restriction and relaxation techniques.

Volume 6, Number 4, August 2010

• 
  Susanne Albers: Editorial note.
• 
  Mohammad Taghi Hajiaghayi, Shang-Hua Teng: Foreword to special issue on SODA 2008.
• 
  Marcel R. Ackermann, Johannes Blömer, Christian Sohler: Clustering for metric and nonmetric distance measures.
• 
  Reid Andersen: A local algorithm for finding dense subgraphs.
• 
  Sergio Cabello, Matt DeVos, Jeff Erickson, Bojan Mohar: Finding one tight cycle.
• 
  Timothy M. Chan: On the bichromatic k-set problem.
• 
  Kenneth L. Clarkson: Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm.
• 
  Yuval Emek, David Peleg, Liam Roditty: A near-linear-time algorithm for computing replacement paths in planar directed graphs.
• 
  Ulrich Faigle, Britta Peis: Two-phase greedy algorithms for some classes of combinatorial linear programs.
• 
  Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Clifford Stein, Zoya Svitkina: On distributing symmetric streaming computations.
• 
  Steve Oudot, Leonidas J. Guibas, Jie Gao, Yue Wang: Geodesic delaunay triangulations in bounded planar domains.
• 
  Bruce M. Kapron, David Kempe, Valerie King, Jared Saia, Vishal Sanwalani: Fast asynchronous Byzantine agreement and leader election with full information.
• 
  Zoya Svitkina: Lower-bounded facility location.
• 
  Virginia Vassilevska Williams: Nondecreasing paths in a weighted graph or: How to optimally read a train schedule.
• 
  Pankaj K. Agarwal, Sariel Har-Peled, Micha Sharir, Yusu Wang: Hausdorff distance under translation for points and balls.
• 
  John Gunnar Carlsson, Benjamin Armbruster, Yinyu Ye: Finding equitable convex partitions of points in a polygon efficiently.

last updated on Thu May 23 04:41:51 2013 by the dblp team
data released under the ODC-BY 1.0 license
see also our legal information page