AuthorsK. Kaya, J. Langguth, I. Panagiotas and B. Uçar
EditorsG. E. Blelloch and I. Finocchi
TitleKarp-Sipser based Kernels for Bipartite Graph Matching
AfilliationScientific Computing
Project(s)Meeting Exascale Computing with Source-to-Source Compilers, UMOD: Understanding and Monitoring Digital Wildfires, Department of High Performance Computing
Publication TypeProceedings, refereed
Year of Publication2020
Conference NameAlgorithm Engineering and Experiment (ALENEX)
PublisherSociety for Industrial and Applied Mathematics

We consider Karp–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.

Citation Key26854

Contact person