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

Graph Theory 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 w...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2013-09, Vol.15 no. 2 (Graph Theory), p.233-242
Main Authors: Demange, Marc, Ekim, Tınaz
Format: Article
Language:English
Subjects:
Computer Science
Discrete Mathematics
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Graph Theory 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.
ISSN:1365-8050
1462-7264
1365-8050
DOI:10.46298/dmtcs.606