Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 9 Issue 2, March 2013

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 (uV, vV, 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...