Cardoso, Domingos M., Korpelainen, Nicholas and Lozin, Vadim V.. (2011) On the complexity of the dominating induced matching problem in hereditary classes of graphs. Discrete Applied Mathematics, Vol.159 (No.7). pp. 521-531. ISSN 0166-218X

Full text not available from this repository.

Abstract

The DOMINATING INDUCED MATCHING problem, also known as EFFICIENT EDGE DOMINATION, is the problem of determining whether a graph has an induced matching that dominates every edge of the graph. This problem is known to be NP-complete. We study the computational complexity of the problem in special graph classes. In the present paper, we identify a critical class for this problem (i.e., a class lying on a "boundary" separating difficult instances of the problem from polynomially solvable ones) and derive a number of polynomial-time results. In particular, we develop polynomial-time algorithms to solve the problem for claw-free graphs and convex graphs. (C) 2010 Elsevier B.V. All rights reserved.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Mathematics
Journal or Publication Title:	Discrete Applied Mathematics
Publisher:	Elsevier Science Ltd.
ISSN:	0166-218X
Date:	6 April 2011
Volume:	Vol.159
Number:	No.7
Page Range:	pp. 521-531
Identification Number:	10.1016/j.dam.2010.03.011
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Funder:	European Community , DIMAP - Center for Discrete Mathematics and its Applications at the University of Warwick
Grant number:	FEDER/POCI/2010 (European Community)
URI:	http://wrap.warwick.ac.uk/id/eprint/41855

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item