Volume 21, pp. 125-133, 2005.

The influence of random number generators on graph partitioning algorithms

Ulrich Elsner

Abstract

Many modern heuristic algorithms rely at least in some part on random numbers. Using graph partitioning algorithms as an example, we demonstrate the often underestimated influence of these random-number generators on the result of the heuristic algorithms. Even methods that rely on random numbers mostly as a tie-breaking tool can deliver very different results depending only on the starting value of the pseudo-random number generator.

Full Text (PDF) [242 KB]

Key words

graph partitioning, heuristic algorithms, pseudo random-number generator

AMS subject classifications

05C85, 90C59, 94C15, 65Y99, 68R10.

< Back