Experimental Algorithmics (JEA)


Search Issue
enter search term and/or author name


Journal of Experimental Algorithmics (JEA), Volume 11, 2006

Section: 1 - Regular Papers

Multipattern string matching with q-grams
Leena Salmela, Jorma Tarhio, Jari Kytöjoki
Article No.: 1.1
DOI: 10.1145/1187436.1187438
We present three algorithms for exact string matching of multiple patterns. Our algorithms are filtering methods, which apply q-grams and bit parallelism. We ran extensive experiments with them and compared them with various versions of...

Cache-efficient string sorting using copying
Ranjan Sinha, Justin Zobel, David Ring
Article No.: 1.2
DOI: 10.1145/1187436.1187439
Burstsort is a cache-oriented sorting technique that uses a dynamic trie to efficiently divide large sets of string keys into related subsets small enough to sort in cache. In our original burstsort, string keys sharing a common prefix were managed...

Cache-Friendly implementations of transitive closure
Michael Penner, Viktor K. Prasanna
Article No.: 1.3
DOI: 10.1145/1187436.1210586
The topic of cache performance has been well studied in recent years. Compiler optimizations exist and optimizations have been done for many problems. Much of this work has focused on dense linear algebra problems. At first glance, the...

Algorithms for dynamic multicast key distribution
Justin Goshi, Richard E. Ladner
Article No.: 1.4
DOI: 10.1145/1187436.1210587
We study the problem of multicast key distribution for group security. Secure group communication systems typically rely on a group key, which is a secret shared among the members of the group. This key is used to provide privacy by encrypting all...

Partitioning planar graphs with costs and weights
Lyudmil Aleksandrov, Hristo Djidjev, Hua Guo, Anil Maheshwari
Article No.: 1.5
DOI: 10.1145/1187436.1210588
A graph separator is a set of vertices or edges whose removal divides an input graph into components of bounded size. This paper describes new algorithms for computing separators in planar graphs as well as techniques that can be used to speed up the...

Heuristics for estimating contact area of supports in layered manufacturing
Ivayio Ilinkin, Ravi Janardan, Michiel Smid, Eric Johnson, Paul Castillo, Jörg Schwerdt
Article No.: 1.6
DOI: 10.1145/1187436.1210589
Layered manufacturing is a technology that allows physical prototypes of three-dimensional(3D) models to be built directly from their digital representation, as a stack of two-dimensional(2D) layers. A key design problem here is the choice of a...

A dynamic topological sort algorithm for directed acyclic graphs
David J. Pearce, Paul H. J. Kelly
Article No.: 1.7
DOI: 10.1145/1187436.1210590
We consider the problem of maintaining the topological order of a directed acyclic graph (DAG) in the presence of edge insertions and deletions. We present a new algorithm and, although this has inferior time complexity compared with the best...

Section: 1 - Regular Papers

JEA Special Section
Sotiris Nikoletseas
Article No.: 2.1
DOI: 10.1145/1187436.1216578

The “real” approximation factor of the MST heuristic for the minimum energy broadcasting
Michele Flammini, Alfredo Navarra, Stephane Perennes
Article No.: 2.10
DOI: 10.1145/1187436.1216587
This paper deals with one of the most studied problems in the last few years in the field of wireless communication in ad-hoc networks. The problem consists of reducing the total energy consumption of wireless radio stations distributed over a given...

A faster branch-and-bound algorithm for the test-cover problem based on set-covering techniques
Torsten Fahle, Karsten Tiemann
Article No.: 2.2
DOI: 10.1145/1187436.1216579
The test-cover problem asks for the minimal number of tests needed to uniquely identify a disease, infection, etc. A collection of branch-and-bound algorithms was proposed by De Bontridder et al. [2002]. Based on their work, we introduce several...

A framework for probabilistic numerical evaluation of sensor networks: A case study of a localization protocol
Pierre Leone, Jose Rolim, Paul Albuquerque, Christian Mazza
Article No.: 2.3
DOI: 10.1145/1187436.1216580
In this paper we show how to use stochastic estimation methods to investigate topological properties of sensor networks as well as the behavior of dynamical processes on these networks. The framework is particularly important to study problems for...

GRASP with path relinking for the weighted MAXSAT problem
Paola Festa, Panos M. Pardalos, Leonidas S. Pitsoulis, Mauricio G. C. Resende
Article No.: 2.4
DOI: 10.1145/1187436.1216581
A GRASP with path relinking for finding good-quality solutions of the weighted maximum satisfiability problem (MAX-SAT) is described in this paper. GRASP, or Greedy Randomized Adaptive Search Procedure, is a randomized multistart metaheuristic,...

Implementing minimum cycle basis algorithms
Kurt Mehlhorn, Dimitrios Michail
Article No.: 2.5
DOI: 10.1145/1187436.1216582
In this paper, we consider the problem of computing a minimum cycle basis of an undirected graph G = (V,E) with n vertices and m edges. We describe an efficient implementation of an...

Rectangle covers revisited computationally
Laura Heinrich-Litan, Marco E. Lübbecke
Article No.: 2.6
DOI: 10.1145/1187436.1216583
We consider the problem of covering an orthogonal polygon with a minimum number of axis-parallel rectangles from a computational point of view. We propose an integer program which is the first general approach to obtain provably optimal solutions to...

Algorithms for pure Nash equilibria in weighted congestion games
Panagiota N. Panagopoulou, Paul G. Spirakis
Article No.: 2.7
DOI: 10.1145/1187436.1216584
In large-scale or evolving networks, such as the Internet, there is no authority possible to enforce a centralized traffic management. In such situations, game theory, and especially the concepts of Nash equilibria and congestion games [Rosenthal...

Partitioning graphs to speedup Dijkstra's algorithm
Rolf H. Möhring, Heiko Schilling, Birk Schütz, Dorothea Wagner, Thomas Willhalm
Article No.: 2.8
DOI: 10.1145/1187436.1216585
We study an acceleration method for point-to-point shortest-path computations in large and sparse directed graphs with given nonnegative arc weights. The acceleration method is called the arc-flag approach and is based on Dijkstra's algorithm....

Integrating coordinated checkpointing and recovery mechanisms into DSM synchronization barriers
Azzedine Boukerche, Alba Cristina Magalhaes Alves De Melo
Article No.: 2.9
DOI: 10.1145/1187436.1216586
Distributed shared memory (DSM) creates an abstraction of a physical shared memory that parallel programmers can access. Most recent software DSM systems provide relaxed-memory models that guarantee consistency only at synchronization operations,...