The labeled perfect matching in bipartite graphs |
| |
Authors: | Jérôme Monnot |
| |
Affiliation: | LAMSADE CNRS, Université Paris-Dauphine, Place du Maréchal De Lattre de Tassigny, F-75775 Paris Cedex 16, France |
| |
Abstract: | In this paper, we deal with both the complexity and the approximability of the labeled perfect matching problem in bipartite graphs. Given a simple graph G=(V,E) with |V|=2n vertices such that E contains a perfect matching (of size n), together with a color (or label) function , the labeled perfect matching problem consists in finding a perfect matching on G that uses a minimum or a maximum number of colors. |
| |
Keywords: | Labeled matching Bipartite graphs NP-complete Approximate algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|