Name
Abstract | ||
|---|---|---|
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. 663, 210-213 2015 |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1002/net.21624 | Networks |
Keywords | Field | DocType |
matching,matching preclusion,robustness,recoverability | Symmetric difference,Discrete mathematics,Graph,Mathematical optimization,Combinatorics,Matching preclusion,Matching (graph theory),Robustness (computer science),Mathematics | Journal |
Volume | Issue | ISSN |
66 | 3 | 0028-3045 |
Citations | PageRank | References |
2 | 0.41 | 16 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mitre Dourado | 1 | 90 | 18.43 |
| Dirk Meierling | 2 | 56 | 11.55 |
| Lucia Draque Penso | 3 | 196 | 20.46 |
| Dieter Rautenbach | 4 | 946 | 138.87 |
| Fábio Protti | 5 | 357 | 46.14 |
| Aline Ribeiro de Almeida | 6 | 6 | 1.58 |