enter search term and/or author name
Expander flows, geometric embeddings and graph partitioning
Sanjeev Arora, Satish Rao, Umesh Vazirani
Article No.: 5
We give a O(&sqrt;log n)-approximation algorithm for the sparsest cut, edge expansion, balanced separator, and graph conductance problems. This improves the O(log n)-approximation of Leighton and Rao (1988). We use a...
Polynomial flow-cut gaps and hardness of directed cut problems
Julia Chuzhoy, Sanjeev Khanna
Article No.: 6
We study the multicut and the sparsest cut problems in directed graphs. In the multicut problem, we are a given an n-vertex graph G along with k source-sink pairs, and the goal is to find the minimum cardinality subset of...
The gene evolution model and computing its associated probabilities
Lars Arvestad, Jens Lagergren, Bengt Sennblad
Article No.: 7
Phylogeny is both a fundamental tool in biology and a rich source of fascinating modeling and algorithmic problems. Today's wealth of sequenced genomes makes it increasingly important to understand evolutionary events such as duplications, losses,...
Multi-linear formulas for permanent and determinant are of super-polynomial size
Article No.: 8
An arithmetic formula is multilinear if the polynomial computed by each of its subformulas is multilinear. We prove that any multilinear arithmetic formula for the permanent or the determinant of an n × n matrix is of size...
An O(n log n) algorithm for maximum st-flow in a directed planar graph
Glencora Borradaile, Philip Klein
Article No.: 9
We give the first correct O(n log n) algorithm for finding a maximum st-flow in a directed planar graph. After a preprocessing step that consists in finding single-source shortest-path distances in the dual, the...
This article presents a method for constructing hardware structures that perform a fixed permutation on streaming data. The method applies to permutations that can be represented as linear mappings on the bit-level representation of the data...