The labeled perfect matching in bipartite graphs

作     者：Monnot, J 

作者机构：Univ Paris 09 LAMSADE CNRS F-75775 Paris France 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2005年第96卷第3期

页      面：81-88页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：labeled matching bipartite graphs NP-complete approximate algorithms 

摘      要：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 vertical bar V vertical bar = 2n vertices such that E contains a perfect matching (of size n), together with a color (or label) function L: E - {c(1),..., C-q}, the labeled perfect matching problem consists in finding a perfect matching on G that uses a minimum or a maximum number of colors. (c) 2005 Elsevier B.V. All rights reserved.