enter search term and/or author name
Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication
Oren Weimann, Raphael Yuster
Article No.: 14
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...
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
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
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...
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
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. . They further showed that the problem is...