Search ACM DL

Search Issue

enter search term and/or author name

Section:

**Locally Compressed Suffix Arrays**

Rodrigo González, Gonzalo Navarro, Héctor Ferrada

Article No.: 1.1

DOI: 10.1145/2594408

We introduce a compression technique for suffix arrays. It is sensitive to the compressibility of the text and *local*, meaning that random portions of the suffix array can be decompressed by accessing mostly contiguous memory areas. This...

**Randomized Rounding in the Presence of a Cardinality Constraint**

Benjamin Doerr, Magnus Wahlström

Article No.: 1.2

DOI: 10.1145/2594409

We consider the problem of generating randomized roundings that satisfy a single cardinality constraint and admit Chernoff-type large deviation bounds for weighted sums of the variables. That this can be done efficiently was proven by Srinivasan...

**Efficient Matching for Column Intersection Graphs**

B. O. Fagginger Auer, R. H. Bisseling

Article No.: 1.3

DOI: 10.1145/2616587

To improve the quality and efficiency of hypergraph-based matrix partitioners, we investigate high-quality matchings in column intersection graphs of large sparse binary matrices. We show that such algorithms have a natural decomposition in an...

**Satisfiability by Maxwell-Boltzmann and Bose-Einstein Statistical Distributions**

Claudio Angione, Annalisa Occhipinti, Giuseppe Nicosia

Article No.: 1.4

DOI: 10.1145/2629498

Recent studies in theoretical computer science have exploited new algorithms and methodologies based on statistical physics for investigating the structure and the properties of the Satisfiability (SAT) problem. We propose a characterization of...

**An Experimental Study on Approximating k Shortest Simple Paths**

Asaf Frieder, Liam Roditty

Article No.: 1.5

DOI: 10.1145/2630068

We have conducted an extensive experimental study on approximation algorithms for computing *k* shortest simple paths in weighted directed graphs. Very recently, Bernstein [2010] presented an algorithm that computes a 1 + ϵ...

**An Audit Tool for Genome Rearrangement Algorithms**

Gustavo Rodrigues Galvão, Zanoni Dias

Article No.: 1.7

DOI: 10.1145/2661633

We consider the combinatorial problem of sorting a permutation using a minimum number of rearrangement events, which finds application in the estimation of evolutionary distance between species. Many variants of this problem, which we generically...

**On a Model of Virtual Address Translation**

Tomasz Jurkiewicz, Kurt Mehlhorn

Article No.: 1.9

DOI: 10.1145/2656337

Modern computers are not Random Access Machines (RAMs). They have a memory hierarchy, multiple cores, and a virtual memory. We address the computational cost of the address translation in the virtual memory. The starting point for our work on...

Section: **Regular Papers**

**Editorial**

Ralf Klasing

Article No.: 2.1

DOI: 10.1145/2677196

**Advanced Coarsening Schemes for Graph Partitioning**

Ilya Safro, Peter Sanders, Christian Schulz

Article No.: 2.2

DOI: 10.1145/2670338

The graph partitioning problem is widely used and studied in many practical and theoretical applications. Today, multilevel strategies represent one of the most effective and efficient generic frameworks for solving this problem on large-scale...

**General Document Retrieval in Compact Space**

Gonzalo Navarro, Simon J. Puglisi, Daniel Valenzuela

Article No.: 2.3

DOI: 10.1145/2670128

Given a collection of documents and a query pattern, *document retrieval* is the problem of obtaining documents that are relevant to the query. The collection is available beforehand so that a data structure, called an index, can be built on...

**Engineering Efficient Paging Algorithms**

Gabriel Moruz, Andrei Negoescu, Christian Neumann, Volker Weichert

Article No.: 2.4

DOI: 10.1145/2670127

In the field of online algorithms, paging is a well-studied problem. LRU is a simple paging algorithm that incurs few cache misses and supports efficient implementations. Algorithms outperforming LRU in terms of cache misses exist but are in...

**Efficient Computation of Shortest Paths in Time-Dependent Multi-Modal Networks**

Dominik Kirchler, Leo Liberti, Roberto Wolfler Calvo

Article No.: 2.5

DOI: 10.1145/2670126

We consider shortest paths on time-dependent multimodal transportation networks in which restrictions or preferences on the use of certain modes of transportation may arise. We model restrictions and preferences by means of regular languages....

**Paired and Altruistic Kidney Donation in the UK**: Algorithms and Experimentation

David F. Manlove, Gregg O’malley

Article No.: 2.6

DOI: 10.1145/2670129

We study the computational problem of identifying optimal sets of kidney exchanges in the UK. We show how to expand an integer programming-based formulation due to Roth et al. [2007] in order to model the criteria that constitute the UK definition...

**Candidate Sets for Alternative Routes in Road Networks**

Dennis Luxen, Dennis Schieferdecker

Article No.: 2.7

DOI: 10.1145/2674395

We study the computation of good alternatives to the shortest path in road networks. Our approach is based on single via-node routing on top of contraction hierarchies and achieves superior quality and efficiency compared to previous methods. We...

Section: **Regular Papers**

**Introduction to Special Issue ALENEX'12**

David A. Bader, Petra Mutzel

Article No.: 3.1

DOI: 10.1145/2721893

**User-Constrained Multimodal Route Planning**

Julian Dibbelt, Thomas Pajor, Dorothea Wagner

Article No.: 3.2

DOI: 10.1145/2699886

In the multimodal route planning problem, we are given multiple transportation networks (e.g., pedestrian, road, public transit) and ask for a best *integrated* journey between two points. The main challenge is that a seemingly optimal...

**Experiments on Density-Constrained Graph Clustering**

Robert Görke, Andrea Kappes, Dorothea Wagner

Article No.: 3.3

DOI: 10.1145/2638551

Clustering a graph means identifying internally dense subgraphs that are only sparsely interconnected. Formalizations of this notion lead to measures that quantify the quality of a clustering and to algorithms that actually find clusterings....

**Fast Compressed Tries through Path Decompositions**

Roberto Grossi, Giuseppe Ottaviano

Article No.: 3.4

DOI: 10.1145/2656332

Tries are popular data structures for storing a set of strings, where common prefixes are represented by common root-to-node paths. More than 50 years of usage have produced many variants and implementations to overcome some of their limitations....