@misc {28395,
	title = {Shared-Memory Implementation of the Karp- Sipser Kernelization Process},
	howpublished = {SIAM ACDA, Richland (virtual)},
	year = {2021},
	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.},
	author = {Langguth, Johannes and Panagiotas, Ioannis and U{\c c}ar, Bora}
}
@inproceedings {28398,
	title = {Shared-memory Implementation of the Karp-Sipser Kernelization Process},
	journal = {28th edition of the IEEE International Conference on High Performance Computing, Data, and Analytics (HiPC 2021)},
	year = {2021},
	month = {12/2021},
	pages = {71-80},
	publisher = {IEEE},
	address = {Bangalore, India},
	author = {Langguth, Johannes and Panagiotas, Ioannis and U{\c c}ar, Bora}
}
@inproceedings {26854,
	title = {Karp-Sipser based Kernels for Bipartite Graph Matching},
	journal = {Algorithm Engineering and Experiment (ALENEX)},
	year = {2020},
	pages = {134-145},
	publisher = {Society for Industrial and Applied Mathematics},
	abstract = {We consider Karp{\textendash}Sipser, a well known matching heuristic in the context of data reduction for the max- imum cardinality matching problem. We describe an efficient implementation as well as modifications to reduce its time complexity in worst case instances, both in theory and in practical cases. We compare experimentally against its widely used simpler variant and show cases for which the full algorithm yields better performance.},
	author = {Kaya, Kamer and Langguth, Johannes and Panagiotas, Ioannis and U{\c c}ar, Bora},
	editor = {Guy E. {Blelloch} and Finocchi, Irene}
}
