enter search term and/or author name
Editorial: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016 Special Issue
Arnab Bhattacharyya, Fabrizio Grandoni, Aleksandar Nikolov, Barna Saha, Saket Saurabh, Aravindan Vijayaraghavan, Qin Zhang
Article No.: 26
The Subtree Isomorphism problem asks whether a given tree is contained in another given tree. The problem is of fundamental importance and has been studied since the 1960s. For some variants, e.g., ordered trees, near-linear time...
The problem of finding large cliques in random graphs and its “planted” variant, where one wants to recover a clique of size ω ≫ log (n) added to an Erdős-Rényi graph G ∼...
CoveringLSH: Locality-Sensitive Hashing without False Negatives
Article No.: 29
We consider a new construction of locality-sensitive hash functions for Hamming space that is covering in the sense that is it guaranteed to produce a collision for every pair of vectors within a given radius r. The construction is...
Improved Deterministic Algorithms for Linear Programming in Low Dimensions
Timothy M. CHAN
Article No.: 30
Chazelle and Matoušek [J. Algorithms, 1996] presented a derandomization of Clarkson’s sampling-based algorithm [J. ACM, 1995] for solving linear programs with n constraints and d variables in...
A Faster Subquadratic Algorithm for Finding Outlier Correlations
Matti Karppa, Petteri Kaski, Jukka Kohonen
Article No.: 31
We study the problem of detecting outlier pairs of strongly correlated variables among a collection of n variables with otherwise weak pairwise correlations. After normalization, this task amounts to the geometric task where we are...
Deterministic Algorithms for Submodular Maximization Problems
Niv Buchbinder, Moran Feldman
Article No.: 32
Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area, most algorithms are randomized, and in...
A spanner H of a weighted undirected graph G is a “sparse” subgraph that approximately preserves distances between every pair of vertices in G. We refer to H as a δ-spanner of G for some...
Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, MichaŁ Pilipczuk, Marcin Wrochna
Article No.: 34
We investigate the complexity of several fundamental polynomial-time solvable problems on graphs and on matrices, when the given instance has low treewidth; in the case of matrices, we consider the treewidth of the graph formed by non-zero...
Subexponential Parameterized Algorithm for I
Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, MichaŁ Pilipczuk
Article No.: 35
In the I
Let V be a set of n points in Rd, which we call voters. A point p ∈ Rd is preferred over another point p′ ∈ Rd by a voter υ ∈ V if...
Erratum: Approximating Minimum-Cost Connectivity Problems via Uncrossable Bifamilies
Article No.: 37
There are two errors in our article “Approximating Minimum-Cost Connectivity Problems via Uncrossable Bifamilies” (ACM Transactions on Algorithms (TALG), 9(1), Article No. 1, 2012). In that article, we consider the...
Exploring the Complexity of Layout Parameters in Tournaments and Semicomplete Digraphs
Florian Barbero, Christophe Paul, MichaŁ Pilipczuk
Article No.: 38
A simple digraph is semicomplete if for any two of its vertices u and v, at least one of the arcs (u,v) and (v,u) is present. We study the complexity of computing two layout parameters of...
Data Structures for Weighted Matching and Extensions to b-matching and f-factors
Harold N. Gabow
Article No.: 39
This article shows the weighted matching problem on general graphs can be solved in time O(n(m + n log n)) for n and m the number of vertices and edges, respectively. This was previously known only...