Karp-Sipser based kernels for bipartite graph matching

Kaya, Kamer and Langguth, Johannes and Panagiotas, Ioannis and Uçar, Bora (2020) Karp-Sipser based kernels for bipartite graph matching. In: Algorithm Engineering and Experiments (ALENEX 2020), Hilton Salt Lake City Center, Salt Lake City, Utah, U.S.

[thumbnail of 1.9781611976007.11.pdf] PDF
Restricted to Registered users only

Download (683kB) | Request a copy


We consider Karp–Sipser, a well-known matching heuristic in the context of data reduction for the maximum 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.
Item Type: Papers in Conference Proceedings
Subjects: Q Science > QA Mathematics > QA075 Electronic computers. Computer science
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences > Basic Sciences > Mathematics
Depositing User: Kamer Kaya
Date Deposited: 25 Aug 2021 15:38
Last Modified: 01 Aug 2023 14:13
URI: https://research.sabanciuniv.edu/id/eprint/41942

Actions (login required)

View Item
View Item