enter search term and/or author name
Motorcycle graphs: Stochastic properties motivate an efficient yet simple implementation
Stefan Huber, Martin Held
Article No.: 1.3
In this article, we study stochastic properties of a geometric setting that underpins random motorcycle graphs and use it to motivate a simple but very efficient algorithm for computing motorcycle graphs. An analysis of the mean trace length of...
Indexing methods for approximate dictionary searching: Comparative analysis
Article No.: 1.1
The primary goal of this article is to survey state-of-the-art indexing methods for approximate dictionary searching. To improve understanding of the field, we introduce a taxonomy that classifies all methods into direct methods and...
An experimental comparison of single-sided preference matching algorithms
Article No.: 1.4
We experimentally study the problem of assigning applicants to posts. Each applicant provides a preference list, which may contain ties, ranking a subset of the posts. Different optimization criteria may be defined, which depend on the desired...
In practical applications, algorithms for the classic version of the hospitals residents problem (the many-one version of the stable marriage problem) may have to be extended to accommodate the needs of couples who wish to be allocated to...
Effective out-of-core parallel delaunay mesh refinement using off-the-shelf software
Andriy Kot, Andrey N. Chernikov, Nikos P. Chrisochoides
Article No.: 1.5
We present three related out-of-core parallel mesh generation algorithms and their implementations for small size computational clusters. Computing out-of-core permits to solve larger problems than otherwise possible on the same hardware setup....
Harvey and Ginsberg's limited discrepancy search (LDS) is based on the assumption that costly heuristic mistakes are made early in the search process. Consequently, LDS repeatedly probes the state space, going against the heuristic (i.e.,...
Generating constrained random graphs using multiple edge switches
Lionel Tabourier, Camille Roth, Jean-Philippe Cointet
Article No.: 1.7
The generation of random graphs using edge swaps provides a reliable method to draw uniformly random samples of sets of graphs respecting some simple constraints (e.g., degree distributions). However, in general, it is not necessarily possible to...
Approximation algorithms for speeding up dynamic programming and denoising aCGH data
Charalampos E. Tsourakakis, Richard Peng, Maria A. Tsiarli, Gary L. Miller, Russell Schwartz
Article No.: 1.8
The development of cancer is largely driven by the gain or loss of subsets of the genome, promoting uncontrolled growth or disabling defenses against it. Denoising array-based Comparative Genome Hybridization (aCGH) data is an important...
Computing elevation maxima by searching the gauss sphere
Bei Wang, Herbert Edelsbrunner, Dmitriy Morozov
Article No.: 2.2
The elevation function on a smoothly embedded 2-manifold in ℝ3 reflects the multiscale topography of cavities and protrusions as local maxima. The function has been useful in identifying coarse docking configurations for...
Multilevel local search algorithms for modularity clustering
Randolf Rotta, Andreas Noack
Article No.: 2.3
Modularity is a widely used quality measure for graph clusterings. Its exact maximization is NP-hard and prohibitively expensive for large graphs. Popular heuristics first perform a coarsening phase, where local search starting from singleton...
psort is the fastest sorting software according to the PennySort benchmark, sorting 181GB of data in 2008 and 224GB in 2009 for $0.01 of computer time. This article details its internals, and the careful fitting of its architecture...
Theory and practice of monotone minimal perfect hashing
Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna
Article No.: 3.2
Minimal perfect hash functions have been shown to be useful to compress data in several data management tasks. In particular, order-preserving minimal perfect hash functions (Fox et al. 1991) have been used to retrieve the position of a key in...
Quasirandom rumor spreading: An experimental analysis
Benjamin Doerr, Tobias Friedrich, Marvin Künnemann, Thomas Sauerwald
Article No.: 3.3
We empirically analyze two versions of the well-known “randomized rumor spreading” protocol to disseminate a piece of information in networks. In the classical model, in each round, each informed node informs a random neighbor. In...
Two-dimensional R-trees are a class of spatial index structures in which objects are arranged to enable fast window queries: report all objects that intersect a given query window. One of the most successful methods of arranging the objects in...
Solving maximum flow problems on real-world bipartite graphs
Cosmin Silvestru Negrucşeri, Mircea BOGDAN Pacsoşi, Barbara Stanley, Clifford Stein, Cristian George Strat
Article No.: 3.5
In this article, we present an experimental study of several maximum-flow algorithms in the context of unbalanced bipartite networks. Our experiments are motivated by a real-world problem of managing reservation-based inventory in Google...
Dealing with large hidden constants: engineering a planar steiner tree PTAS
Siamak Tazari, Matthias Müller-Hannemann
Article No.: 3.6
We present the first attempt on implementing a highly theoretical polynomial-time approximation scheme (PTAS) with huge hidden constants, namely, the PTAS for Steiner tree in planar graphs by Borradaile, Klein, and Mathieu (2009). Whereas this...