Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 10 Issue 3, June 2014

Algebraic Algorithms for Linear Matroid Parity Problems
Ho Yee Cheung, Lap Chi Lau, Kai Man Leung
Article No.: 10
DOI: 10.1145/2601066

We present fast and simple algebraic algorithms for the linear matroid parity problem and its applications. For the linear matroid parity problem, we obtain a simple randomized algorithm with running time O(mrω-1),...

Approximate Privacy: Foundations and Quantification
Joan Feigenbaum, Aaron D. Jaggard, Michael Schapira
Article No.: 11
DOI: 10.1145/2601067

The proliferation of online sensitive data about individuals and organizations makes concern about the privacy of these data a top priority. There have been many formulations of privacy and, unfortunately, many negative results about the...

Deterministic Rendezvous, Treasure Hunts, and Strongly Universal Exploration Sequences
Amnon Ta-Shma, Uri Zwick
Article No.: 12
DOI: 10.1145/2601068

We obtain several improved solutions for the deterministic rendezvous problem in general undirected graphs. Our solutions answer several problems left open by Dessmark et al. We also introduce an interesting variant of the rendezvous...

Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Philip N. Klein
Article No.: 13
DOI: 10.1145/2601070
We improve the approximation ratios for two optimization problems in planar graphs. For node-weighted Steiner tree, a classical network-optimization problem, the best achievable approximation ratio in general graphs is Θ (log n), and...

Faster Algorithms for Semi-Matching Problems
Jittat Fakcharoenphol, Bundit Laekhanukit, Danupon Nanongkai
Article No.: 14
DOI: 10.1145/2601071

We consider the problem of finding semi-matching in bipartite graphs, which is also extensively studied under various names in the scheduling literature. We give faster algorithms for both weighted and unweighted cases.

For the...

Fast Convergence for Consensus in Dynamic Networks
T.-H. Hubert Chan, Li Ning
Article No.: 15
DOI: 10.1145/2601072

In this article, we study the convergence time required to achieve consensus in dynamic networks. In each timestep, a node's value is updated to some weighted average of its neighbors and its old values. We study the case when the underlying...

Fully Functional Static and Dynamic Succinct Trees
Gonzalo Navarro, Kunihiko Sadakane
Article No.: 16
DOI: 10.1145/2601073

We propose new succinct representations of ordinal trees and match various space/time lower bounds. It is known that any n-node static tree can be represented in 2n + o(n) bits so that a number of operations on the...