Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 11 Issue 2, November 2014

Approximating Rooted Steiner Networks
Joseph Cheriyan, Bundit Laekhanukit, Guyslain Naves, Adrian Vetta
Article No.: 8
DOI: 10.1145/2650183

The Directed Steiner Tree (DST) problem is a cornerstone problem in network design. We focus on the generalization of the problem with higher connectivity requirements. The problem with one root and two sinks is APX-hard. The problem with one root...

Quasirandom Rumor Spreading
Benjamin Doerr, Tobias Friedrich, Thomas Sauerwald
Article No.: 9
DOI: 10.1145/2650185

We propose and analyze a quasirandom analogue of the classical push model for disseminating information in networks (“randomized rumor spreading”). In the classical model, in each round, each informed vertex chooses a neighbor at...

Deterministic Network Exploration by Anonymous Silent Agents with Local Traffic Reports
Yoann Dieudonné, Andrzej Pelc
Article No.: 10
DOI: 10.1145/2594581

A team consisting of an unknown number of mobile agents starting from different nodes of an unknown network, possibly at different times, have to explore the network: Every node must be visited by at least one agent, and all agents must eventually...

Dynamic Ray Stabbing
Yufei Tao
Article No.: 11
DOI: 10.1145/2559153

We consider maintaining a dynamic set S of N horizontal segments in ℝ2 such that, given a vertical ray Q in ℝ2, the segments in S intersecting Q can be reported efficiently. In the...

Two-Dimensional Parameterized Matching
Richard Cole, Carmit Hazay, Moshe Lewenstein, Dekel Tsur
Article No.: 12
DOI: 10.1145/2650220

Two equal-length strings, or two equal-sized two-dimensional texts, parameterize match (p-match) if there is a one-one mapping (relative to the alphabet) of their characters. Two-dimensional parameterized matching is the task...

Kernelization Lower Bounds Through Colors and IDs
Michael Dom, Daniel Lokshtanov, Saket Saurabh
Article No.: 13
DOI: 10.1145/2650261

In parameterized complexity, each problem instance comes with a parameter k, and a parameterized problem is said to admit a polynomial kernel if there are polynomial time preprocessing rules that reduce the input instance to an...

Minimizing Movement: Fixed-Parameter Tractability
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dániel Marx
Article No.: 14
DOI: 10.1145/2650247

We study an extensive class of movement minimization problems that arise from many practical scenarios but so far have little theoretical study. In general, these problems involve planning the coordinated motion of a collection of agents...

Faster Parameterized Algorithms Using Linear Programming
Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
Article No.: 15
DOI: 10.1145/2566616

We investigate the parameterized complexity of Vertex Cover parameterized by the difference between the size of the optimal solution and the value of the linear programming (LP) relaxation of the problem. By carefully analyzing the...