ACM DL

Algorithms (TALG)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Algorithms (TALG), Volume 8 Issue 4, September 2012

Replacement paths and k simple shortest paths in unweighted directed graphs
Liam Roditty, Uri Zwick
Article No.: 33
DOI: 10.1145/2344422.2344423

Let G = (V,E) be a directed graph and let P be a shortest path from s to t in G. In the replacement paths problem, we are required to find, for every edge e on P, a shortest...

All-pairs shortest paths for unweighted undirected graphs in o(mn) time
Timothy M. Chan
Article No.: 34
DOI: 10.1145/2344422.2344424

We revisit the all-pairs-shortest-paths problem for an unweighted undirected graph with n vertices and m edges. We present new algorithms with the following running times:

{ O(mn/log n) if m...

Fully dynamic randomized algorithms for graph spanners
Surender Baswana, Sumeet Khurana, Soumojit Sarkar
Article No.: 35
DOI: 10.1145/2344422.2344425

Spanner of an undirected graph G = (V,E) is a subgraph that is sparse and yet preserves all-pairs distances approximately. More formally, a spanner with stretch t ∈ ℕ is a subgraph (V,ES),...

The effectiveness of stackelberg strategies and tolls for network congestion games
Chaitanya Swamy
Article No.: 36
DOI: 10.1145/2344422.2344426

It is well known that in a network with arbitrary (convex) latency functions that are a function of edge traffic, the worst-case ratio, over all inputs, of the system delay caused due to selfish behavior versus the system delay of the optimal...

How to meet asynchronously (almost) everywhere
Jurek Czyzowicz, Andrzej Pelc, Arnaud Labourel
Article No.: 37
DOI: 10.1145/2344422.2344427

Two mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly infinite, unknown connected graph or in an unknown connected terrain in the plane. Agents are modeled as points, and the route of each of them only depends on...

Kernel(s) for problems with no kernel: On out-trees with many leaves
Daniel Binkele-Raible, Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Yngve Villanger
Article No.: 38
DOI: 10.1145/2344422.2344428

The k-Leaf Out-Branching problem is to find an out-branching, that is a rooted oriented spanning tree, with at least k leaves in a given digraph. The problem has recently received much attention from the viewpoint of parameterized...

An online scalable algorithm for average flow time in broadcast scheduling
Sungjin Im, Benjamin Moseley
Article No.: 39
DOI: 10.1145/2344422.2344429

In this article, the online pull-based broadcast model is considered. In this model, there are n pages of data stored at a server and requests arrive for pages online. When the server broadcasts page p, all outstanding...

An FPTAS for the minimum total weighted tardiness problem with a fixed number of distinct due dates
George Karakostas, Stavros G. Kolliopoulos, Jing Wang
Article No.: 40
DOI: 10.1145/2344422.2344430

Given a sequencing of jobs on a single machine, each one with a weight, processing time, and a due date, the tardiness of a job is the time needed for its completion beyond its due date. We present an FPTAS for the basic scheduling problem of...

Parallel pipelined filter ordering with precedence constraints
Amol Deshpande, Lisa Hellerstein
Article No.: 41
DOI: 10.1145/2344422.2344431

In the parallel pipelined filter ordering problem, we are given a set of n filters that run in parallel. The filters need to be applied to a stream of elements, to determine which elements pass all filters. Each filter has a rate...

Succinct ordinal trees based on tree covering
Meng He, J. Ian Munro, Srinivasa Rao Satti
Article No.: 42
DOI: 10.1145/2344422.2344432

Various methods have been used to represent a tree on n nodes in essentially the information-theoretic minimum space while supporting various navigational operations in constant time, but different representations usually support different...

Range searching on uncertain data
Pankaj K. Agarwal, Siu-Wing Cheng, Ke Yi
Article No.: 43
DOI: 10.1145/2344422.2344433

Querying uncertain data has emerged as an important problem in data management due to the imprecise nature of many measurement data. In this article, we study answering range queries over uncertain data. Specifically, we are given a collection...

The smoothed complexity of edit distance
Alexandr Andoni, Robert Krauthgamer
Article No.: 44
DOI: 10.1145/2344422.2344434

We initiate the study of the smoothed complexity of sequence alignment, by proposing a semi-random model of edit distance between two input strings, generated as follows: First, an adversary chooses two binary strings of length d and a...