Treffer: The Labeled perfect matching in bipartite graphs

Title:
The Labeled perfect matching in bipartite graphs
Authors:
Monnot, Jérôme
Contributors:
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris Sciences et Lettres (PSL)-Université Paris Sciences et Lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)
Source:
Information Processing Letters. :1-9
Publisher Information:
CCSD; Elsevier, 2005.
Publication Year:
2005
Collection:
collection:CNRS
collection:UNIV-DAUPHINE
collection:LAMSADE-DAUPHINE
collection:TDS-MACS
collection:PSL
collection:UNIV-DAUPHINE-PSL
Subject Terms:
labeled matching, bipartite graphs, NP-complete, approximate algorithms, [INFO.INFO-DM]Computer Science [cs], Discrete Mathematics [cs.DM]
Original Identifier:
HAL: hal-00007798
Document Type:
Zeitschrift article<br />Journal articles
Language:
English
ISSN:
0020-0190
Access URL:
https://hal.science/hal-00007798
https://hal.science/hal-00007798v1/document
https://hal.science/hal-00007798v1/file/LabeledMatching_prelim_.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.hal.00007798v1
Database:
HAL

Weitere Informationen

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 $L:E\rightarrow \{c_1,\ldots,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.