Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-00980770
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Wednesday, May 7, 2014 - 3:42:11 PM
Last modification on : Wednesday, September 23, 2020 - 4:29:58 AM
Long-term archiving on: : Thursday, August 7, 2014 - 10:36:59 AM

File

2133-8309-1-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00980770, version 1

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⟩

Share

Metrics

Record views

502

Files downloads

1121