enter search term and/or author name
We give an algorithm to morph between two planar orthogonal drawings of a graph, preserving planarity and orthogonality. The morph uses a quadratic number of steps, where each step is a linear morph (a linear interpolation between two drawings)....
Finding small separators in linear time via treewidth reduction
Dáaniel Marx, Barry O'sullivan, Igor Razgon
Article No.: 30
We present a method for reducing the treewidth of a graph while preserving all of its minimal s-t separators up to a certain fixed size k. This technique allows us to solve s-t
Optimal lower bounds for projective list update algorithms
Christoph Ambühl, Bernd Gärtner, Bernhard von Stengel
Article No.: 31
The list update problem is a classical online problem, with an optimal competitive ratio that is still open, known to be somewhere between 1.5 and 1.6. An algorithm with competitive ratio 1.6, the smallest known to date, is COMB, a randomized...
Online auction is the essence of many modern markets, particularly networked markets, in which information about goods, agents, and outcomes is revealed over a period of time, and the agents must make irrevocable decisions without knowing future...
We analyze the Matrix Berlekamp/Massey algorithm, which generalizes the Berlekamp/Massey algorithm [Massey 1969] for computing linear generators of scalar sequences. The Matrix Berlekamp/Massey algorithm computes a minimal matrix generator of a...
Corrigendum: Improved results for data migration and open shop scheduling
Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai
Article No.: 34
In Gandhi et al. , we gave an algorithm for the data migration and non-deterministic open shop scheduling problems in the minimum sum version, that was claimed to achieve a 5.06-approximation. Unfortunately, it was pointed to us by Maxim...