Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 7 Issue 4, September 2011

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