@misc{16464,
  author = {Johannes Langguth and Ioannis Panagiotas and Bora U{\c c}ar},
  title = {Shared-Memory Implementation of the Karp- Sipser Kernelization Process},
  abstract = {We investigate the parallelization of the Karp-Sipser ker- nelization technique, which constitutes the central part of the well known Karp-Sipser heuristic for the maximum cardinality matching problem. The technique reduces a given problem instance to a smaller but equivalent one, by a series of two operations: vertex removal, and merg- ing/unifying two vertices. The operation of merging two vertices poses the principal challenge in parallelizing the technique. We describe an algorithm that minimizes the need for synchronization and present an efficient shared- memory parallel implementation. Using extensive experi- ments on a variety of multicore CPUs, we show that our implementation scales well up to 32 cores on one socket.},
  year = {2021},
  journal = {SIAM ACDA, Richland (virtual)},
}