The Library
On the complexity of the dominating induced matching problem in hereditary classes of graphs
Tools
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. doi:10.1016/j.dam.2010.03.011 ISSN 0166-218X.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.dam.2010.03.011
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, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Discrete Applied Mathematics | ||||
Publisher: | Elsevier Science Ltd. | ||||
ISSN: | 0166-218X | ||||
Official Date: | 6 April 2011 | ||||
Dates: |
|
||||
Volume: | Vol.159 | ||||
Number: | No.7 | ||||
Page Range: | pp. 521-531 | ||||
DOI: | 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) |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |