Minimum colored maximum matching is NP-hard on trees

Pré-Publication, Document De Travail Année : 2018

(1)

Jonas Sénizergues

Laboratoire de Recherche en Informatique

A reduction of 3-SAT to Minimum colored maximum matching.

Mathématique discrète [cs.DM] Complexité [cs.CC]

Fichier principal

MinCMaxM.pdf (177.19 Ko)

Origine : Fichiers produits par l'(les) auteur(s)

https://hal.science/hal-01827567

Soumis le : lundi 2 juillet 2018-14:42:26

Dernière modification le : vendredi 9 février 2024-03:25:28

Archivage à long terme le : lundi 1 octobre 2018-06:33:53

hal-01827567 , version 1 (02-07-2018)

Jonas Sénizergues. Minimum colored maximum matching is NP-hard on trees. 2018. ⟨hal-01827567⟩

CNRS UMR8623 CENTRALESUPELEC TDS-MACS UNIV-PARIS-SACLAY LISN GS-COMPUTER-SCIENCE LISN-GALAC

432 Consultations

84 Téléchargements