Search ACM DL

Search Issue

enter search term and/or author name

**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,E _{S}*),...

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