A backtracking-based algorithm for hypertree decomposition
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
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, then the LZ-index takes 4...
Computing an approximation of the 1-center problem on weighted terrain surfaces
In this article, we discuss the problem of determining a meeting point of a set of scattered robots R = {r1, r2,…,rs} in a weighted terrain P, which has n > s triangular faces. Our algorithmic approach is to produce a discretization of P by producing a ...
Multilevel algorithms for linear ordering problems
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
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 very large grid terrain in ...
A general buffer scheme for the windows scheduling problem
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 latency.
...
Multiword atomic read/write registers on multiprocessor systems
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 atomic ...
Succinct backward-DAWG-matching
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
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 algorithms ...
Fast computation of empirically tight bounds for the diameter of massive graphs
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
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 1%; in such ...
Compressed text indexes: From theory to practice
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 required several ...
A domain decomposition algorithm for constraint satisfaction
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 is that ...
An improved heuristic for computing short integral cycle bases
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 applications in the periodic event ...
Automated reaction mapping
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 problem. ...
Data reduction and exact algorithms for clique cover
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, allow for ...
An experimental study of point location in planar arrangements in CGAL
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 naïve approach, a “...
Summarizing spatial data streams using ClusterHulls
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, called ClusterHull, ...
Engineering multilevel overlay graphs for shortest-path queries
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 multilevel overlay graph used in Schulz et al. [2002] to speed up ...
