Search ACM DL

Search Issue

enter search term and/or author name

Section:

**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: **Graph Theory**

**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: **Graph Theory**

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

Section: **Graph Theory**

**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: **Graph Theory**

**(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: **Graph Theory**

**Invited Articles Foreword**

Eva Tardos

Article No.: 45e

DOI: 10.1145/3018097

Section: **Graph Theory**

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

Section: **Graph Theory**

**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: **Graph Theory**

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