Search ACM DL

Search Issue

enter search term and/or author name

**A backtracking-based algorithm for hypertree decomposition**

Georg Gottlob, Marko Samer

Article No.: 1

DOI: 10.1145/1412228.1412229

Hypertree decompositions of hypergraphs are a generalization of tree decompositions of graphs. The corresponding hypertree-width is a measure for the acyclicity and therefore an indicator for the tractability of the associated computation problem....

**Implementing the LZ-index**: Theory versus practice

Gonzalo Navarro

Article No.: 2

DOI: 10.1145/1412228.1412230

The LZ-index is a theoretical proposal of a lightweight data structure for text indexing, based on the Ziv-Lempel trie. If a text of *u* characters over an alphabet of size σ is compressible to *n* symbols using the LZ78 algorithm,...

**Computing an approximation of the 1-center problem on weighted terrain surfaces**

Mark A. Lanthier, Doron Nussbaum, Tsuo-Jung Wang

Article No.: 3

DOI: 10.1145/1412228.1412231

In this article, we discuss the problem of determining a meeting point of a set of scattered robots *R* &equls; {*r*_{1}, *r*_{2},…,*r _{s}*} in a weighted terrain P, which has

**Multilevel algorithms for linear ordering problems**

Ilya Safro, Dorit Ron, Achi Brandt

Article No.: 4

DOI: 10.1145/1412228.1412232

Linear ordering problems are combinatorial optimization problems that deal with the minimization of different functionals by finding a suitable permutation of the graph vertices. These problems are widely used and studied in many practical and...

**Computing visibility on terrains in external memory**

Herman Haverkort, Laura Toma, Yi Zhuang

Article No.: 5

DOI: 10.1145/1412228.1412233

Given an arbitrary viewpoint *v* and a terrain, the visibility map or viewshed of *v* is the set of points in the terrain that are visible from *v*. In this article we consider the problem of computing the viewshed of a point on a...

**A general buffer scheme for the windows scheduling problem**

Amotz Bar-Noy, Richard E. Ladner, Jacob Christensen, Tami Tamir

Article No.: 6

DOI: 10.1145/1412228.1412234

Broadcasting is an efficient alternative to unicast for delivering popular on-demand media requests. Broadcasting schemes that are based on windows scheduling algorithms provide a way to satisfy all requests with both low bandwidth and low...

**Multiword atomic read/write registers on multiprocessor systems**

Andreas Larsson, Anders Gidenstam, Phuong H. Ha, Marina Papatriantafilou, Philippas Tsigas

Article No.: 7

DOI: 10.1145/1412228.1455262

Modern multiprocessor systems offer advanced synchronization primitives, built in hardware, to support the development of efficient parallel algorithms. In this article, we develop a simple and efficient algorithm, the READERSFIELD algorithm, for...

**Succinct backward-DAWG-matching**

Kimmo Fredriksson

Article No.: 8

DOI: 10.1145/1412228.1455263

We consider single and multiple string matching in small space and optimal average time. Our algorithm is based on the combination of compressed self-indexes and Backward-DAWG-Matching (BDM) algorithm. We consider several implementation techniques...

**Efficiently implementing maximum independent set algorithms on circle graphs**

Nicholas Nash, Sylvain Lelait, David Gregg

Article No.: 9

DOI: 10.1145/1412228.1455265

Circle graphs are an important class of graph with applications in a number of areas, including compiler optimization, VLSI design and computational geometry. In this article, we provide an experimental evaluation of the two most efficient...

**Fast computation of empirically tight bounds for the diameter of massive graphs**

Clémence Magnien, Matthieu Latapy, Michel Habib

Article No.: 10

DOI: 10.1145/1412228.1455266

The diameter of a graph is among its most basic parameters. Since a few years ago, it moreover became a key issue to compute it for massive graphs in the context of complex network analysis. However, known algorithms, including the ones producing...

**Inversion-sensitive sorting algorithms in practice**

Amr Elmasry, Abdelrahman Hammad

Article No.: 11

DOI: 10.1145/1412228.1455267

We study the performance of the most practical inversion-sensitive internal sorting algorithms. Experimental results illustrate that adaptive AVL sort consumes the fewest number of comparisons unless the number of inversions is less than...

**Compressed text indexes**: From theory to practice

Paolo Ferragina, Rodrigo González, Gonzalo Navarro, Rossano Venturini

Article No.: 12

DOI: 10.1145/1412228.1455268

A *compressed full-text self-index* represents a text in a compressed form and still answers queries efficiently. This represents a significant advancement over the (full-)text indexing techniques of the previous decade, whose indexes...

**A domain decomposition algorithm for constraint satisfaction**

Wady Naanaa

Article No.: 13

DOI: 10.1145/1412228.1455269

This article presents a domain decomposition algorithm for solving constraint satisfactions problems (CSPs). The proposed algorithm relies on a weak form of neighborhood substitutability referred to as directional substitutability. The main idea...

**An improved heuristic for computing short integral cycle bases**

Telikepalli Kavitha, Katakam Vamsi Krishna

Article No.: 14

DOI: 10.1145/1412228.1498696

In this article, we consider the problem of constructing low-weight integral cycle bases in a directed graph *G* = (*V*, *E*) with nonnegative edge weights. It has been shown that low-weight integral cycle bases have...

**Automated reaction mapping**

John D. Crabtree, Dinesh P. Mehta

Article No.: 15

DOI: 10.1145/1412228.1498697

Automated reaction mapping is a fundamental first step in the analysis of chemical reactions and opens the door to the development of sophisticated chemical kinetic tools. This article formulates the reaction mapping problem as an optimization...

**Preface**

Rajeev Raman, Matt Stallmann

Article No.: 1

DOI: 10.1145/1412228.1412235

**Data reduction and exact algorithms for clique cover**

Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier

Article No.: 2

DOI: 10.1145/1412228.1412236

To cover the edges of a graph with a minimum number of cliques is an NP-hard problem with many applications. For this problem we develop efficient and effective polynomial-time data reduction rules that, combined with a search tree algorithm,...

**An experimental study of point location in planar arrangements in CGAL**

Idit Haran, Dan Halperin

Article No.: 3

DOI: 10.1145/1412228.1412237

We study the performance in practice of various point-location algorithms implemented in CGAL (the Computational Geometry Algorithms Library), including a newly devised *landmarks* algorithm. Among the other algorithms studied are: a...

**Summarizing spatial data streams using ClusterHulls**

John Hershberger, Nisheeth Shrivastava, Subhash Suri

Article No.: 4

DOI: 10.1145/1412228.1412238

We consider the following problem: given an on-line, possibly unbounded stream of two-dimensional (2D) points, how can we summarize its spatial distribution or *shape* using a small, bounded amount of memory? We propose a novel scheme,...

**Engineering multilevel overlay graphs for shortest-path queries**

Martin Holzer, Frank Schulz, Dorothea Wagner

Article No.: 5

DOI: 10.1145/1412228.1412239

An overlay graph of a given graph *G* = (*V*, *E*) on a subset *S* ⊆ *V* is a graph with vertex set *S* and edges corresponding to shortest paths in *G*. In particular, we consider variations of the...