The Library
From matchings to independent sets
Tools
Tools
Tools
Lozin, Vadim V. (2016) From matchings to independent sets. Discrete Applied Mathematics, 231 . pp. 4-14. doi:10.1016/j.dam.2016.04.012 ISSN 0166-218X.
![[img]](https://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
WRAP_m2i-revision.pdf - Accepted Version - Requires a PDF viewer. Download (592Kb) |
Official URL: http://dx.doi.org/10.1016/j.dam.2016.04.012
Abstract
In 1965, Jack Edmonds proposed his celebrated polynomial-time algorithm to find a maximum matching in a graph. It is well-known that finding a maximum matching in G is equivalent to finding a maximum independent set in the line graph of G. For general graphs, the maximum independent set problem is NP-hard. What makes this problem easy in the class of line graphs and what other restrictions can lead to an efficient solution of the problem? In the present paper, we analyze these and related questions. We also review various techniques that may lead to efficient algorithms for the maximum independent set problem in restricted graph families, with a focus given to augmenting graphs and graph transformations. Both techniques have been used in the solution of Edmonds to the maximum matching problem, i.e. in the solution to the maximum independent set problem in the class of line graphs. We survey various results that exploit these techniques beyond the line graphs.
| Item Type: | Journal Article | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||||
| Library of Congress Subject Headings (LCSH): | Polynomials , Set theory | ||||||||||
| Journal or Publication Title: | Discrete Applied Mathematics | ||||||||||
| Publisher: | Elsevier Science Ltd. | ||||||||||
| ISSN: | 0166-218X | ||||||||||
| Official Date: | 20 November 2016 | ||||||||||
| Dates: |
|
||||||||||
| Volume: | 231 | ||||||||||
| Page Range: | pp. 4-14 | ||||||||||
| DOI: | 10.1016/j.dam.2016.04.012 | ||||||||||
| Status: | Peer Reviewed | ||||||||||
| Publication Status: | Published | ||||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||||
| Date of first compliant deposit: | 3 May 2016 | ||||||||||
| Date of first compliant Open Access: | 24 August 2016 | ||||||||||
| Funder: | Engineering and Physical Sciences Research Council (EPSRC) | ||||||||||
| Grant number: | EP/L020408/1 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
