Search ACM DL

Search Issue

enter search term and/or author name

**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^{+} → Z* ^{d}* 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,

**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...