The Library
Combinatorics and algorithms for augmenting graphs
Tools
Dabrowski, Konrad K., Lozin, Vadim V., de Werra, Dominique and Zamaraev, Viktor (2016) Combinatorics and algorithms for augmenting graphs. Graphs and Combinatorics, 32 (4). pp. 1339-1352. doi:10.1007/s00373-015-1660-0 ISSN 0911-0119.
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.1007/s00373-015-1660-0
Abstract
The notion of augmenting graphs generalizes Berge’s idea of augmenting chains, which was used by Edmonds in his celebrated solution of the maximum matching problem. This problem is a special case of the more general maximum independent set (MIS) problem. Recently, the augmenting graph approach has been successfully applied to solve MIS in various other special cases. However, our knowledge of augmenting graphs is still very limited and we do not even know what the minimal infinite classes of augmenting graphs are. In the present paper, we find an answer to this question and apply it to extend the area of polynomial-time solvability of the maximum independent set problem
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||
Journal or Publication Title: | Graphs and Combinatorics | ||||||
Publisher: | Springer Japan KK | ||||||
ISSN: | 0911-0119 | ||||||
Official Date: | July 2016 | ||||||
Dates: |
|
||||||
Volume: | 32 | ||||||
Number: | 4 | ||||||
Page Range: | pp. 1339-1352 | ||||||
DOI: | 10.1007/s00373-015-1660-0 | ||||||
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 |