Search ACM DL

Search Issue

enter search term and/or author name

**Expander flows, geometric embeddings and graph partitioning**

Sanjeev Arora, Satish Rao, Umesh Vazirani

Article No.: 5

DOI: 10.1145/1502793.1502794

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

DOI: 10.1145/1502793.1502795

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

DOI: 10.1145/1502793.1502796

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**

Ran Raz

Article No.: 8

DOI: 10.1145/1502793.1502797

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

DOI: 10.1145/1502793.1502798

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...

**Permuting streaming data using RAMs**

Markus Püschel, Peter A. Milder, James C. Hoe

Article No.: 10

DOI: 10.1145/1502793.1502799

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...