The Library
Dominating induced matchings in graphs without a skew star
Tools
Korpelainen, Nicholas, Lozin, Vadim V. and Purcell, Christopher (2014) Dominating induced matchings in graphs without a skew star. Journal of Discrete Algorithms, Volume 26 . pp. 45-55. doi:10.1016/j.jda.2013.11.002 ISSN 1570-8667.
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.jda.2013.11.002
Abstract
We study the problem of determining whether a graph G has an induced matching that dominates every edge of the graph, which is also known as efficient edge domination. This problem is known to be NP-complete in general graphs, but it can be solved in polynomial time for graphs in some special classes, such as weakly chordal, P7-free or claw-free graphs. In the present paper we extend the polynomial-time solvability of the problem from claw-free graphs to graphs without a skew star, where a skew star is a tree with exactly three vertices of degree 1 being of distance 1,2,3 from the only vertex of degree 3.
Item Type: | Journal Article | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||||
Journal or Publication Title: | Journal of Discrete Algorithms | ||||||||||
Publisher: | Elsevier BV | ||||||||||
ISSN: | 1570-8667 | ||||||||||
Official Date: | May 2014 | ||||||||||
Dates: |
|
||||||||||
Volume: | Volume 26 | ||||||||||
Page Range: | pp. 45-55 | ||||||||||
DOI: | 10.1016/j.jda.2013.11.002 | ||||||||||
Status: | Peer Reviewed | ||||||||||
Publication Status: | Published | ||||||||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |