enter search term and/or author name
Multipattern string matching with q-grams
Jorma Tarhio, Jari Kytöjoki, Leena Salmela
Article No.: 1.1
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
Justin Zobel, David Ring, Ranjan Sinha
Article No.: 1.2
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
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
Richard E. Ladner, Justin Goshi
Article No.: 1.4
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, Anil Maheshwari, Hua Guo, Hristo Djidjev
Article No.: 1.5
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
Jörg Schwerdt, Ravi Janardan, Ivayio Ilinkin, Paul Castillo, Eric Johnson, Michiel Smid
Article No.: 1.6
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
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...
The “real” approximation factor of the MST heuristic for the minimum energy broadcasting
Michele Flammini, Stephane Perennes, Alfredo Navarra
Article No.: 2.10
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
Karsten Tiemann, Torsten Fahle
Article No.: 2.2
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. . Based on their work, we introduce several...
A framework for probabilistic numerical evaluation of sensor networks: A case study of a localization protocol
Paul Albuquerque, Christian Mazza, Jose Rolim, Pierre Leone
Article No.: 2.3
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
Leonidas S. Pitsoulis, Paola Festa, Panos M. Pardalos, Mauricio G. C. Resende
Article No.: 2.4
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
Dimitrios Michail, Kurt Mehlhorn
Article No.: 2.5
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
Marco E. Lübbecke, Laura Heinrich-Litan
Article No.: 2.6
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
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, Thomas Willhalm, Dorothea Wagner, Birk Schütz, Heiko Schilling
Article No.: 2.8
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
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,...