ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 56 Issue 2, April 2009

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