Perfect Matching Under Precedence Constraints

Networks, vol. 87, pp. 175–190

Abstract

ABSTRACT In this article, we motivate and define variants of perfect matching under precedence constraints where a perfect matching is built incrementally and precedence constraints ensure that an edge may only be added to the matching if the edge's predecessor vertices have already been covered. We study the complexity of the problem and particularly consider ‐canonical precedence constraints where only edges that are “close” to the current matching may be added to the matching. For the ‐hard perfect matching under 1‐canonical precedence constraints, we identify polynomial‐time solvable cases.

Authors 2

1. Christina Büsing Aachen Lehr‐ und Forschungsgebiet Kombinatorische Optimierung

   RWTH Aachen University

   Affiliation as printed

   Lehr‐ und Forschungsgebiet Kombinatorische Optimierung RWTH Aachen University Aachen Germany

   Lehr- und Forschungsgebiet Kombinatorische Optimierung, RWTH Aachen University, Aachen, Germany

2. Corinna Mathwieser corresponding Aachen Lehr‐ und Forschungsgebiet Kombinatorische Optimierung

   RWTH Aachen University

   Affiliation as printed

   Lehr‐ und Forschungsgebiet Kombinatorische Optimierung RWTH Aachen University Aachen Germany

   Lehr- und Forschungsgebiet Kombinatorische Optimierung, RWTH Aachen University, Aachen, Germany