Show simple item record

dc.contributor.authorLacroix, Mathieu
dc.contributor.authorMahjoub, Ali Ridha
dc.contributor.authorMartin, Sébastien
dc.contributor.authorPicouleau, Christophe
dc.date.accessioned2012-02-21T16:03:39Z
dc.date.available2012-02-21T16:03:39Z
dc.date.issued2012
dc.identifier.issn0304-3975
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/8212
dc.language.isoenen
dc.subjectBipartite graph
dc.subjectMatching
dc.subjectStructural analysis problem
dc.subjectNP-complete
dc.subjectTripartite graph
dc.subjectStable set
dc.subjectBlocker
dc.subject.ddc511en
dc.titleOn the NP-completeness of the perfect matching free subgraph problem
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherConservatoire National des Arts et Métiers, CEDRIC;France
dc.description.abstractenGiven a bipartite graph G=(U∪V,E) such that ∣U∣=∣V∣ and every edge is labelled true or false or both, the perfect matching free subgraph problem is to determine whether or not there exists a subgraph of G containing, for each node u of U, either all the edges labelled true or all the edges labelled false incident to u, and which does not contain a perfect matching. This problem arises in the structural analysis of differential-algebraic systems. The purpose of this paper is to show that this problem is NP-complete. We show that the problem is equivalent to the stable set problem in a restricted case of tripartite graphs. Then we show that the latter remains NP-complete in that case. We also prove the NP-completeness of the related minimum blocker problem in bipartite graphs with perfect matching.
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol423
dc.relation.isversionofjnldate2012
dc.relation.isversionofjnlpages25-29
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.tcs.2011.12.065
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2018-02-13T12:35:07Z
hal.person.labIds*
hal.person.labIds989*
hal.person.labIds989*
hal.person.labIds*
hal.identifierhal-01497061*


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record