Robust recoverable perfect matchings | Zendy

Dourado Mitre Costa | Zendy; Meierling Dirk | Zendy; Penso Lucia D. | Zendy; Rautenbach Dieter | Zendy; Protti Fabio | Zendy; de Almeida Aline Ribeiro | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research