ACM DL

Algorithms (TALG)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Algorithms (TALG), Volume 8 Issue 2, April 2012

Dotted interval graphs
Yonatan Aumann, Moshe Lewenstein, Oren Melamud, Ron Pinter, Zohar Yakhini
Article No.: 9
DOI: 10.1145/2151171.2151172

We introduce a generalization of interval graphs, which we call Dotted Interval Graphs (DIG). A dotted interval graph is an intersection graph of arithmetic progressions (dotted intervals). Coloring of dotted interval graphs naturally arises in...

Succinct geometric indexes supporting point location queries
Prosenjit Bose, Eric Y. Chen, Meng He, Anil Maheshwari, Pat Morin
Article No.: 10
DOI: 10.1145/2151171.2151173

We propose designing data structures called succinct geometric indexes of negligible space (more precisely, o(n) bits) that support geometric queries in optimal time, by taking advantage of the n points in the dataset permuted...

A precise analysis of Cuckoo hashing
Michael Drmota, Reinhard Kutzelnigg
Article No.: 11
DOI: 10.1145/2151171.2151174

Cuckoo hashing was introduced by Pagh and Rodler in 2001. Its main feature is that it provides constant worst-case search time. The aim of this article is to present a precise average case analysis of Cuckoo hashing. In particular, we determine...

Multidimensional online tracking
Ke Yi, Qin Zhang
Article No.: 12
DOI: 10.1145/2151171.2151175

We propose and study a new class of online problems, which we call online tracking. Suppose an observer, say Alice, observes a multivalued function f: Z+ → Zd over time in an online fashion,...

The price of anarchy in network creation games
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Hamid Mahini, Morteza Zadimoghaddam
Article No.: 13
DOI: 10.1145/2151171.2151176

We study Nash equilibria in the setting of network creation games introduced recently by Fabrikant, Luthra, Maneva, Papadimitriou, and Shenker. In this game we have a set of selfish node players, each creating some incident links, and the goal is...

Elimination graphs
Yuli Ye, Allan Borodin
Article No.: 14
DOI: 10.1145/2151171.2151177

In this article we study graphs with inductive neighborhood properties. Let P be a graph property, a graph G = (V, E) with n vertices is said to have an inductive neighborhood property with respect to P if there...

On the query complexity of testing orientations for being Eulerian
Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman, Orly Yahalom
Article No.: 15
DOI: 10.1145/2151171.2151178

We consider testing directed graphs Eulerianity in the orientation model introduced in Halevy et al. [2005]. Despite the local nature of the Eulerian property, it turns out to be significantly harder to test than other properties studied in the...

How to trim a MST: A 2-Approximation algorithm for minimum cost-tree cover
Toshihiro Fujito
Article No.: 16
DOI: 10.1145/2151171.2151179

The minimum cost-tree cover problem is to compute a minimum cost-tree T in a given connected graph G with costs on the edges, such that the vertices spanned by T form a vertex cover for G. The problem is supposed...

On approximating multicriteria TSP
Bodo Manthey
Article No.: 17
DOI: 10.1145/2151171.2151180

We present approximation algorithms for almost all variants of the multicriteria traveling salesman problem (TSP).

First, we devise randomized approximation algorithms for multicriteria maximum traveling salesman problems (Max-TSP). For...

The traveling salesman problem in bounded degree graphs
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
Article No.: 18
DOI: 10.1145/2151171.2151181

We show that the traveling salesman problem in bounded-degree graphs can be solved in time O((2-ε)n), where ε > 0 depends only on the degree bound but not on the number of cities, n. The algorithm...

On the hardness of losing weight
Andrei Krokhin, Dániel Marx
Article No.: 19
DOI: 10.1145/2151171.2151182

We study the complexity of local search for the Boolean constraint satisfaction problem (CSP), in the following form: given a CSP instance, that is, a collection of constraints, and a solution to it, the question is whether there is a better...