Premium
Robust recoverable perfect matchings
Author(s) -
Dourado Mitre Costa,
Meierling Dirk,
Penso Lucia D.,
Rautenbach Dieter,
Protti Fabio,
de Almeida Aline Ribeiro
Publication year - 2015
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21624
Subject(s) - matching (statistics) , combinatorics , graph , computer science , set (abstract data type) , mathematics , mathematical optimization , algorithm , statistics , programming language
We study perfect matchings M in graphs G that have the two properties of being robust as well as recoverable ; where robust means that the failure of a set F ′ of not too many edges of G can be compensated, and recoverable means that this compensation can be done in an efficient way, that is, G − F ′ has a perfect matching M ′ for which the symmetric difference of M and M ′ is small. We establish the hardness of several related algorithmic problems and identify some tractable cases. Among others we show the hardness of the well known matching preclusion number of a graph. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(3), 210–213 2015