 |
Discrete Mathematics & Theoretical Computer Science |
Marc Demange ; Tinaz Ekim - A note on the NP-hardness of two matching problems in induced subgrids
dmtcs:606 - Discrete Mathematics & Theoretical Computer Science, September 4, 2013, Vol. 15 no. 2 - https://doi.org/10.46298/dmtcs.606A note on the NP-hardness of two matching problems in induced subgridsArticle
- 1 ESSEC Business School
- 2 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision
Graph Theory
[en]
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.
Source: HAL:hal-00980770v1
Volume: Vol. 15 no. 2
Section: Graph Theory
Published on: September 4, 2013
Imported on: April 11, 2012
Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
- Source : OpenAIRE Graph
- Kararlı Evlilik Ve Eşkerteli Biparti Çizgelerde En Küçük Maksimal Eşleme Problemi; Funder: Türkiye Bilimsel ve Teknolojik Araştırma Kurumu; Code: 108M616
Consultation statistics
This page has been seen 607 times.
This article's PDF has been downloaded 979 times.