enter search term and/or author name
Three-coloring triangle-free planar graphs in linear time
Zdeněk Dvořák, Ken-Ichi Kawarabayashi, Robin Thomas
Article No.: 41
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
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
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
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
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
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 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
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...
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...
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...
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
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...
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...
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...