enter search term and/or author name
Algebraic Algorithms for Linear Matroid Parity Problems
Ho Yee Cheung, Lap Chi Lau, Kai Man Leung
Article No.: 10
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
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
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
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...
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.
Fast Convergence for Consensus in Dynamic Networks
T.-H. Hubert Chan, Li Ning
Article No.: 15
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
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...