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

Demange, M and Ekim, T 2013, 'A note on the NP-hardness of two matching problems in induced subgrids', Discrete Mathematics and Theoretical Computer Science, vol. 15, no. 2, pp. 233-242.


Document type: Journal Article
Collection: Journal Articles

Title A note on the NP-hardness of two matching problems in induced subgrids
Author(s) Demange, M
Ekim, T
Year 2013
Journal name Discrete Mathematics and Theoretical Computer Science
Volume number 15
Issue number 2
Start page 233
End page 242
Total pages 10
Publisher Chapman & Hall
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.
Subject Mathematical Sciences not elsewhere classified
Information and Computing Sciences not elsewhere classified
Keyword(s) Edge dominating set
Grid graphs
Maximum induced matching
Minimum maximal matching
Copyright notice © 2013 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France
ISSN 1365-8050
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 1 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 2 times in Scopus Article | Citations
Access Statistics: 132 Abstract Views  -  Detailed Statistics
Created: Wed, 21 Jan 2015, 08:28:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us