The server is under maintenance between 08:00 to 12:00 (GMT+08:00), and please visit later.
We apologize for any inconvenience caused
Login  | Sign Up  |  Oriprobe Inc. Feed
China/Asia On Demand
Journal Articles
Laws/Policies/Regulations
Companies/Products
Bookmark and Share
NP-Completeness of Induced Matching Problem and Co-NP-Completeness of Induced Matching Extendable Problem
Author(s): 
Pages: 76-80
Year: Issue:  1
Journal: OR TRANSACTIONS

Keyword:  MatchingIM-extendableco-NP-completeanalysis;
Abstract: A matching M of a graph G is induced, if M is an induced subgraph of G. A graph G is induced matching extendable (simply IM-extendable), if every induced matching M of G is included in a perfect matching of G. In this paper we will prove the following results. (1) The problem "given a graph G and a positive integer r, determine whether there is an induced matching M of G such that |M| ≥ r" is NP-complete for claw-free graphs. (2) The problem "determine whether a given graph is IM-extendable" is co-NP-complete for graphs with diameter 2 and bipartite graphs with diameter 3 but linearly solvable for complete multi-partite graphs.
Related Articles
No related articles found