Search ACM DL

Search Issue

enter search term and/or author name

**Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication**

Oren Weimann, Raphael Yuster

Article No.: 14

DOI: 10.1145/2438645.2438646

A *distance sensitivity oracle* of an *n*-vertex graph *G* = (*V*,*E*) is a data structure that can report shortest paths when edges of the graph fail. A query (*u* ∈ *V*, *v* ∈ *V*, *S*...

**Approximating the Girth**

Liam Roditty, Roei Tov

Article No.: 15

DOI: 10.1145/2438645.2438647

This article considers the problem of computing a minimum weight cycle in weighted undirected graphs. Given a weighted undirected graph *G* = (*V*,*E*,*w*), let *C* be a minimum weight cycle of *G*, let...

**An O(log n)-Approximation Algorithm for the Edge-Disjoint Paths Problem in Eulerian Planar Graphs**

Ken-Ichi Kawarabayashi, Yusuke Kobayashi

Article No.: 16

DOI: 10.1145/2438645.2438648

In this article, we study an approximation algorithm for the maximum edge-disjoint paths problem. In this problem, we are given a graph and a collection of pairs of vertices, and the objective is to find the maximum number of pairs that can be...

**Delays Induce an Exponential Memory Gap for Rendezvous in Trees**

Pierre Fraigniaud, Andrzej Pelc

Article No.: 17

DOI: 10.1145/2438645.2438649

The aim of rendezvous in a graph is meeting of two mobile agents at some node of an unknown anonymous connected graph. In this article, we focus on rendezvous in trees, and, analogously to the efforts that have been made for solving the...

**Speed Scaling with an Arbitrary Power Function**

Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs

Article No.: 18

DOI: 10.1145/2438645.2438650

This article initiates a theoretical investigation into online scheduling problems with speed scaling where the allowable speeds may be discrete, and the power function may be arbitrary, and develops algorithmic analysis techniques for this...

**Approximation Algorithms for a Minimization Variant of the Order-Preserving Submatrices and for Biclustering Problems**

Dorit S. Hochbaum, Asaf Levin

Article No.: 19

DOI: 10.1145/2438645.2438651

Finding a largest Order-Preserving SubMatrix, OPSM, is an important problem arising in the discovery of patterns in gene expression. Ben-Dor et al. formulated the problem in Ben-Dor et al. [2003]. They further showed that the problem is...