Volume 5,
Number 1,
November 2008
- Eric Torng, Jason McCullough:
SRPT optimally utilizes faster machines to minimize flow time.
- Michael H. Goldwasser, Mark Pedigo:
Online nonpreemptive scheduling of equal-length jobs on two identical machines.
- William Aiello, Alexander Kesselman, Yishay Mansour:
Competitive buffer management for shared-memory switches.
- Pankaj K. Agarwal, Haim Kaplan, Micha Sharir:
Kinetic and dynamic data structures for closest pair and all nearest neighbors.
- Pankaj K. Agarwal, Micha Sharir, Emo Welzl:
Algorithms for center and Tverberg points.
- Fabrizio Grandoni, Jochen Könemann, Alessandro Panconesi:
Distributed weighted vertex cover via maximal matchings.
- Sundar Vishwanathan:
On hard instances of approximate vertex cover.
- Daniel Berend, Steven Skiena, Yochai Twitto:
Combinatorial dominance guarantees for problems with infeasible solutions.
- Fedor V. Fomin, Fabrizio Grandoni, Artem V. Pyatkin, Alexey A. Stepanov:
Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications.
- Sang-il Oum:
Approximating rank-width and clique-width quickly.
- Andreas Brandstädt, Van Bang Le, R. Sritharan:
Structure and linear-time recognition of 4-leaf powers.
- Xin Chen, Lan Liu, Zheng Liu, Tao Jiang:
On the minimum common integer partition problem.
- Dany Azriel, Noam Solomon, Shay Solomon:
On an infinite family of solvable Hanoi graphs.
- Amr Elmasry, Claus Jensen, Jyrki Katajainen:
Multipartite priority queues.
Volume 5,
Number 2,
March 2009
- David Eppstein:
Testing bipartiteness of geometric intersection graphs.
- Ke Chen, Haim Kaplan, Micha Sharir:
Online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles.
- Laurent Alonso, Edward M. Reingold:
Average-case analysis of some plurality algorithms.
- Amotz Bar-Noy, Sudipto Guha, Yoav Katz, Joseph Naor, Baruch Schieber, Hadas Shachnai:
Throughput maximization of real-time scheduling with batching.
- Yuval Rabani, Gabriel Scalosub:
Bicriteria approximation tradeoff for the node-cost budget problem.
- Guojun Li, Xiaotie Deng, Ying Xu:
A polynomial-time approximation scheme for embedding hypergraph in a cycle.
- Guy Even, Jon Feldman, Guy Kortsarz, Zeev Nutov:
A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2.
- Sharon Marko, Dana Ron:
Approximating the distance to properties in bounded-degree and general sparse graphs.
- Vincent Berry, Christophe Paul, Sylvain Guillemot, François Nicolas:
Linear time 3-approximation for the MAST problem.
- Anne Condon, Amol Deshpande, Lisa Hellerstein, Ning Wu:
Algorithms for distributional and adversarial pipelined filter ordering problems.
Volume 5,
Number 3,
July 2009
- Harold N. Gabow:
Foreword to special issue on SODA 2007.
- Milan Ruzic:
Making deterministic signatures quickly.
- Robert D. Carr, Goran Konjevod, Greg Little, Venkatesh Natarajan, Ojas Parekh:
Compacting cuts: A new linear formulation for minimum cut.
- Yoav Giyora, Haim Kaplan:
Optimal dynamic vertical ray shooting in rectilinear planar subdivisions.
- David Eppstein:
Squarepants in a tree: Sum of subtree clustering and hyperbolic pants decomposition.
- Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveis Gharan, Morteza Zadimoghaddam:
Minimizing movement.
- Glencora Borradaile, Philip N. Klein, Claire Mathieu:
An O(n log n) approximation scheme for Steiner tree in planar graphs.
- Moses Charikar, Konstantin Makarychev, Yury Makarychev:
Near-optimal algorithms for maximum constraint satisfaction problems.
- Matthew Andrews:
Instability of FIFO in the permanent sessions model at arbitrarily small network loads.
Volume 5,
Number 4,
October 2009
- Leana Golubchik, Sanjeev Khanna, Samir Khuller, Ramakrishna Thurimella, An Zhu:
Approximation algorithms for data placement on parallel disks.
- Sudipto Guha, Andrew McGregor, Suresh Venkatasubramanian:
Sublinear estimation of entropy and information distances.
- Asaf Levin:
A generalized minimum cost k-clustering.
- Martin Farach-Colton, Rohan J. Fernandes, Miguel A. Mosteiro:
Bootstrapping a hop-optimal network in the weak sensor model.
- David Eppstein:
All maximal independent sets and dynamic dominance for sparse graphs.
- Bruce A. Reed, David R. Wood:
A linear-time algorithm to find a separator in a graph excluding a minor.
- Hiro Ito, Kazuo Iwama:
Enumeration of isolated cliques and pseudo-cliques.
- George Karakostas:
A better approximation ratio for the vertex cover problem.
- Daniel Berend, Vladimir Braverman:
A linear algorithm for computing convex hulls for random lines.
- Ming-Yang Kao, Manan Sanghi, Robert T. Schweller:
Randomized fast design of short DNA words.
- David Fernández-Baca, Balaji Venkatachalam:
Parametric analysis for ungapped Markov models of evolution.
- Alexander D. Scott, Gregory B. Sorkin:
Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function.
- Phong Q. Nguyen, Damien Stehlé:
Low-dimensional lattice basis reduction revisited.
Last update Tue Feb 14 04:22:46 2012
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
