Fetching the paper…
Reading the bibliography…
In 1982, Papadimitriou and Yannakakis introduced the Exact Matching (EM) problem where given an edge colored graph, with colors red and blue, and an integer $k$, the goal is to decide whether or not the graph contains a perfect matching with exactly $k$ red edges.
On a routing problem
Richard Bellman · 1958
Earlier work this paper cites.
Maximum matching and a polyhedron with 0, 1-vertices
Jack Edmonds · 1965
Earlier work this paper cites.
The complexity of restricted spanning tree problems
Christos H Papadimitriou and Mihalis Yannakakis · 1982
Earlier work this paper cites.
Maximum matching of given weight in complete and complete bipartite graphs
AV Karzanov · 1987
Earlier work this paper cites.
Matching is as easy as matrix inversion
Ketan Mulmuley, Umesh V Vazirani, and Vijay V Vazirani · 1987
Earlier work this paper cites.
Random pseudo-polynomial algorithms for exact matroid problems
Paolo M. Camerini, Giulia Galbiati, and Francesco Maffioli · 1992
Earlier work this paper cites.
Introduction to the Theory of Complexity
Daniel P Bovet and Pierluigi Crescenzi · 1994
Earlier work this paper cites.
Color-coding
Noga Alon, Raphael Yuster, and Uri Zwick · 1995
Earlier work this paper cites.
On the theory of Pfaffian orientations. I. Perfect matchings and permanents
Anna Galluccio and Martin Loebl · 1999
Earlier work this paper cites.
Matchings in colored bipartite networks
Tongnyoul Yi, Katta G Murty, and Cosimo Spera · 2002
Earlier work this paper cites.
Derandomizing polynomial identity tests means proving circuit lower bounds
Valentine Kabanets and Russell Impagliazzo · 2004
Earlier work this paper cites.
A polynomial time equivalence between DNA sequencing and the exact perfect matching problem
Jacek Błażewicz, Piotr Formanowicz, Marta Kasprzak, Petra Schuurman, and Gerhard J Woeginger · 2007
Cited alongside, same era.
Maximum weight edge-constrained matchings
Irena Rusu · 2008
Cited alongside, same era.
Optimization with more than one budget
Fabrizio Grandoni and Rico Zenklusen · 2010
Cited alongside, same era.
Budgeted matching and budgeted matroid intersection via the gasoline puzzle
André Berger, Vincenzo Bonifaci, Fabrizio Grandoni, and Guido Schäfer · 2011
Cited alongside, same era.
A unified proof for karzanov’s exact matching theorem
Hans-Florian Geerdes and Jácint Szabó · 2011
Cited alongside, same era.
Planarizing gadgets for perfect matching do not exist
Parameterized algorithms
Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh · 2015
Later among the works it cites.
Solving linear equations parameterized by hamming weight
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and Jacobo Torán · 2016
Later among the works it cites.
Algebraic combinatorics
Christopher David Godsil · 2017
Later among the works it cites.
Exact perfect matching in complete graphs
Rohit Gurjar, Arpita Korwar, Jochen Messner, and Thomas Thierauf · 2017
Later among the works it cites.
The matching problem in general graphs is in quasi-nc
Ola Svensson and Jakub Tarnawski · 2017
Later among the works it cites.
Approximation algorithms for minimum norm and ordered optimization problems
Deeparnab Chakrabarty and Chaitanya Swamy · 2019
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, and Thomas Thierauf · 2012
Cited alongside, same era.
Constrained matching problems in bipartite graphs
Monaldo Mastrolilli and Georgios Stamoulis · 2012
Cited alongside, same era.
Almost exact matchings
Raphael Yuster · 2012
Cited alongside, same era.
Bi-criteria and approximation algorithms for restricted matchings
Monaldo Mastrolilli and Georgios Stamoulis · 2014
Cited alongside, same era.
Approximation algorithms for bounded color matchings via convex decompositions
Georgios Stamoulis · 2014
Cited alongside, same era.
An investigation of the recoverable robust assignment problem
Dennis Fischer, Tim A Hartmann, Stefan Lendl, and Gerhard J Woeginger · 2020
Later among the works it cites.
Parameterizing the permanent: Hardness for k _ 8 k\_8 -minor-free graphs
Radu Curticapean and Mingji Xia · 2021
Later among the works it cites.
Exact Matching in Graphs of Bounded Independence Number
Nicolas El Maalouly and Raphael Steiner · 2022
Closest in time.
Exact matching and the top-k perfect matching problem
Nicolas El Maalouly and Lasse Wulf · 2022
Closest in time.