Search ACM DL

Search Issue

enter search term and/or author name

**Multipattern string matching with q-grams**

Jorma Tarhio, Jari Kytöjoki, Leena Salmela

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

**Cache-efficient string sorting using copying**

Justin Zobel, David Ring, Ranjan Sinha

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

Richard E. Ladner, Justin Goshi

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, Anil Maheshwari, Hua Guo, Hristo Djidjev

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

Jörg Schwerdt, Ravi Janardan, Ivayio Ilinkin, Paul Castillo, Eric Johnson, Michiel Smid

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

**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, Stephane Perennes, Alfredo Navarra

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

Karsten Tiemann, Torsten Fahle

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

Paul Albuquerque, Christian Mazza, Jose Rolim, Pierre Leone

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

Leonidas S. Pitsoulis, Paola Festa, Panos M. Pardalos, 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**

Dimitrios Michail, Kurt Mehlhorn

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

Marco E. Lübbecke, Laura Heinrich-Litan

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, Thomas Willhalm, Dorothea Wagner, Birk Schütz, Heiko Schilling

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