JOURNAL OF COMPUTERS (JCP)
ISSN : 1796-203X
Volume : 1    Issue : 6    Date : September 2006

The Matching Predicate and a Filtering Scheme Based on Matroids
Dimitris Magos, Ioannis Mourtos and Leonidas Pitsoulis
Page(s): 37-42
Full Text:
PDF (328 KB)


Abstract
Finding a maximum cardinality matching in a graph is a problem appearing in numerous settings.
The problem asks for a set of edges of maximum cardinality, such that no two edges of this set
have an endpoint in common. The variety of applications of this problem, along with the fact that
several logic predicates can be modelled after it, motivates the study of a related global constraint
in the context of Constraint Programming. In this work, we describe a filtering scheme for such a
predicate based on matroids. Our method guarantees hyper-arc consistency in polynomial time. It
is also applicable to any predicate expressed in terms of an independent system, and remains of
polynomial complexity if there exists a polynomial time algorithm for finding a maximum cardinality
basis of this independent system. Furthermore, we show that this filtering scheme can be
employed to find a maximum cardinality matching.

Index Terms
matching, hyper-arc consistency, matroid intersection