Search ACM DL

Search Issue

enter search term and/or author name

**Philippe flajolet, the father of analytic combinatorics**

Bruno Salvy, Bob Sedgewick, Michele Soria, Wojciech Szpankowski, Brigitte Vallee

Article No.: 40

DOI: 10.1145/2000807.2000808

**Three-coloring triangle-free planar graphs in linear time**

Zdeněk Dvořák, Ken-Ichi Kawarabayashi, Robin Thomas

Article No.: 41

DOI: 10.1145/2000807.2000809

Grötzsch's theorem states that every triangle-free planar graph is 3-colorable, and several relatively simple proofs of this fact were provided by Thomassen and other authors. It is easy to convert these proofs into quadratic-time algorithms...

**Partial convex recolorings of trees and galled networks**: Tight upper and lower bounds

Shlomo Moran, Sagi Snir, Wing-Kin Sung

Article No.: 42

DOI: 10.1145/2000807.2000810

A coloring of a graph is convex if the vertices that pertain to any color induce a connected subgraph; a partial coloring (which assigns colors to a subset of the vertices) is convex if it can be completed to a convex (total) coloring. Convex...

**Geometric clustering**: Fixed-parameter tractability and lower bounds with respect to the dimension

Sergio Cabello, Panos Giannopoulos, Christian Knauer, Dániel Marx, Günter Rote

Article No.: 43

DOI: 10.1145/2000807.2000811

We study the parameterized complexity of the *k*-center problem on a given *n*-point set *P* in &ℝ^{d}, with the dimension *d* as the parameter. We show that the rectilinear 3-center problem is...

**Tight bounds and a fast FPT algorithm for directed Max-Leaf Spanning Tree**

Paul Bonsma, Frederic Dorn

Article No.: 44

DOI: 10.1145/2000807.2000812

An out-tree *T* of a directed graph *D* is a rooted tree subgraph with all arcs directed outwards from the root. An out-branching is a spanning out-tree. By ℓ(*D*) and ℓ_{s}(*D*), we denote the maximum...

**All-pairs shortest paths with a sublinear additive error**

Liam Roditty, Asaf Shapira

Article No.: 45

DOI: 10.1145/2000807.2000813

We show that, for every 0 ≤ *p* ≤ 1, there is an *O*(*n*^{2.575−p/(7.4−2.3p)})-time algorithm that given a directed graph with small positive integer weights, estimates the length of the...

**Fast computation of small cuts via cycle space sampling**

David Pritchard, Ramakrishna Thurimella

Article No.: 46

DOI: 10.1145/2000807.2000814

We describe a new sampling-based method to determine cuts in an undirected graph. For a graph (*V*, *E*), its cycle space is the family of all subsets of *E* that have even degree at each vertex. We prove that with high probability,...

**Broadcast scheduling**: Algorithms and complexity

Jessica Chang, Thomas Erlebach, Renars Gailis, Samir Khuller

Article No.: 47

DOI: 10.1145/2000807.2000815

Broadcast Scheduling is a popular method for disseminating information in response to client requests. There are *n* pages of information, and clients request pages at different times. However, multiple clients can have their requests...

**An improved approximation algorithm for resource allocation**

Gruia Calinescu, Amit Chakrabarti, Howard Karloff, Yuval Rabani

Article No.: 48

DOI: 10.1145/2000807.2000816

We study the problem of finding a most profitable subset of *n* given tasks, each with a given start and finish time as well as profit and resource requirement, that at no time exceeds the quantity *B* of available resource. We show that...

**Memoryless facility location in one pass**

Dimitris Fotakis

Article No.: 49

DOI: 10.1145/2000807.2000817

We present the first one-pass memoryless algorithm for metric Facility Location that maintains a set of facilities approximating the optimal facility configuration within a constant factor. The algorithm is randomized and very simple to state and...

**A new upper bound 2.5545 on 2D Online Bin Packing**

Xin Han, Francis Y. L. Chin, Hing-Fung Ting, Guochuan Zhang, Yong Zhang

Article No.: 50

DOI: 10.1145/2000807.2000818

The 2D Online Bin Packing is a fundamental problem in Computer Science and the determination of its asymptotic competitive ratio has research attention. In a long series of papers, the lower bound of this ratio has been improved from 1.808, 1.856...

**Cake cutting really is not a piece of cake**

Jeff Edmonds, Kirk Pruhs

Article No.: 51

DOI: 10.1145/2000807.2000819

We consider the well-known cake cutting problem in which a protocol wants to divide a cake among *n* ≥ 2 players in such a way that each player believes that they got a fair share. The standard Robertson-Webb model allows the protocol to...

**Succinct indexes for strings, binary relations and multilabeled trees**

Jérémy Barbay, Meng He, J. Ian Munro, Srinivasa Rao Satti

Article No.: 52

DOI: 10.1145/2000807.2000820

We define and design succinct indexes for several abstract data types (ADTs). The concept is to design auxiliary data structures that ideally occupy asymptotically less space than the information-theoretic lower bound on the space required to...

**Fully compressed suffix trees**

Luís M. S. Russo, Gonzalo Navarro, Arlindo L. Oliveira

Article No.: 53

DOI: 10.1145/2000807.2000821

Suffix trees are by far the most important data structure in stringology, with a myriad of applications in fields like bioinformatics and information retrieval. Classical representations of suffix trees require Θ(*n* log *n*) bits...

**Carry propagation in multiplication by constants**

Alexander Izsak, Nicholas Pippenger

Article No.: 54

DOI: 10.1145/2000807.2000822

Suppose that a random *n*-bit number *V* is multiplied by an odd constant *M* ≥ 3, by adding shifted versions of the number *V* corresponding to the 1s in the binary representation of the constant *M*. Suppose further...