ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


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: 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 kn1 − ϵ, ϵ > 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={ (s1,t1),&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...