A Parallel Stochastic Optimization Algorithm for Finding Mappings of the Rectilinear Minimal Crossing Problem

Parallel processing has been a valuable tool for improving the performance of many algorithms. Solving intractable problems is an attractive application of parallel processing. Traditionally, exhaustive search techniques have been used to find solutions to \(NP\)-complete problems. However, the performance benefit of parallelization of exhaustive search algorithms can only provide linear speedup, which is typically of little use as problem complexity increases exponentially with problem size. Genetic algorithms can be useful tools to provide satisfactory results to such problems. This paper presents a genetic algorithm that uses parallel processing in a cooperative fashion to determine mappings for the rectilinear crossing problem. Results from this genetic algorithm are presented which contradict a conjecture that has been open for over 20 years regarding the minimal crossing number for rectilinear graphs.