Search ACM DL

Search Issue

enter search term and/or author name

**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...

**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...

**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 *k* ≤ *n*^{1 − ϵ}, ϵ > 0 a constant, is well understood, we concentrate...

**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...

**(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...

**Invited Articles Foreword**

Eva Tardos

Article No.: 45e

DOI: 10.1145/3018097

**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*={ (*s*_{1},*t*_{1}),&ldots;...

**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...

**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...