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]](https://research.sabanciuniv.edu/style/images/fileicons/application_pdf.png)
PDF
1.9781611976007.11.pdf
Restricted to Registered users only
Download (683kB) | Request a copy
Official URL: http://dx.doi.org/10.1137/1.9781611976007.11
Abstract
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