2 papers
cs.DS2025
Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
Nicolas El Maalouly, Kostas Lakis
The Exact Matching (EM) problem asks whether there exists a perfect matching which uses a prescribed number of red edges in a red/blue edge-colored graph. While there exists a rand…
cs.DS2025
On Finding -th Smallest Perfect Matchings
Nicolas El Maalouly, Sebastian Haslebacher, Adrian Taubner +1
Given an undirected weighted graph and an integer , Exact-Weight Perfect Matching (EWPM) is the problem of finding a perfect matching of weight exactly in . In this p…