Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 63 Issue 5, December 2016

Section: Graph Theory

Polynomial Bounds for the Grid-Minor Theorem
Chandra Chekuri, Julia Chuzhoy
Article No.: 40
DOI: 10.1145/2820609

One of the key results in Robertson and Seymour’s seminal work on graph minors is the grid-minor theorem (also called the excluded grid theorem). The theorem states that for every grid H, every graph whose treewidth is large...

Section: Algorithms 8 Data Structures

Highway Dimension and Provably Efficient Shortest Path Algorithms
Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, Renato F. Werneck
Article No.: 41
DOI: 10.1145/2985473

Computing driving directions has motivated many shortest path algorithms based on preprocessing. Given a graph, the preprocessing stage computes a modest amount of auxiliary data, which is then used to speed up online queries. In practice, the...

Section: Randomized Algorithms 8 Probabilistic Combinatorics

Playing Mastermind With Many Colors
Benjamin Doerr, Carola Doerr, Reto Spöhel, Henning Thomas
Article No.: 42
DOI: 10.1145/2987372

We analyze the general version of the classic guessing game Mastermind with n positions and k colors. Since the case kn1 − ϵ, ϵ > 0 a constant, is well understood, we concentrate...

Section: Probabilistic Combinations

The Local Lemma Is Asymptotically Tight for SAT
Heidi Gebauer, Tibor Szabó, Gábor Tardos
Article No.: 43
DOI: 10.1145/2975386

The Local Lemma is a fundamental tool of probabilistic combinatorics and theoretical computer science, yet there are hardly any natural problems known where it provides an asymptotically tight answer. The main theme of our article is to identify...

Section: Parameterized Complexity, Graph Algorithms, Monadic Second-order Logic

(Meta) Kernelization
Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, Dimitrios M. Thilikos
Article No.: 44
DOI: 10.1145/2973749

In a parameterized problem, every instance I comes with a positive integer k. The problem is said to admit a polynomial kernel if, in polynomial time, one can reduce the size of the instance I to a polynomial in k while...

Section: Invited Articles

Invited Articles Foreword
Eva Tardos
Article No.: 45e
DOI: 10.1145/3018097

Section: Graph Algorithms

A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
Julia Chuzhoy, Shi Li
Article No.: 45
DOI: 10.1145/2893472

In the Edge-Disjoint Paths with Congestion problem (EDPwC), we are given an undirected n-vertex graph G, a collection M={ (s1,t1),&ldots;...

Section: Computational Complexity

Exponential Separation of Information and Communication for Boolean Functions
Anat Ganor, Gillat Kol, Ran Raz
Article No.: 46
DOI: 10.1145/2907939

We show an exponential gap between communication complexity and information complexity by giving an explicit example of a partial boolean function with information complexity ≤ O(k), and distributional communication complexity...

Section: Distributed Computing

Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic, and Faulty Networks
Leonid Barenboim
Article No.: 47
DOI: 10.1145/2979675

We study the distributed (Δ + 1)-vertex-coloring and (2Δ − 1)-edge-coloring problems. These problems are among the most important and intensively studied problems in distributed computing. Despite very intensive research in the...