A note on the NP-hardness of two matching problems in induced subgrids

Abstract : Given a graph, finding the maximal matching of minimum size (MMM) and the induced matching of maximum size (MIM) have been very popular research topics during the last decades. In this paper, we give new complexity results, namely the NP-hardness of MMM and MIM in induced subgrids and we point out some promising research directions. We also sketch the general framework of a unified approach to show the NP-hardness of some problems in subgrids.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.233--242
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00980770
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 7 mai 2014 - 15:42:11
Dernière modification le : jeudi 11 janvier 2018 - 06:17:30
Document(s) archivé(s) le : jeudi 7 août 2014 - 10:36:59

Fichier

2133-8309-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00980770, version 1

Collections

Citation

Marc Demange, Tınaz Ekim. A note on the NP-hardness of two matching problems in induced subgrids. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.233--242. 〈hal-00980770〉

Partager

Métriques

Consultations de la notice

420

Téléchargements de fichiers

307