| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
On the Complexity of the Upper r-Tolerant Edge Cover Problem
Abstract : We consider the problem of computing edge covers that are tolerant to a certain number of edge deletions. We call the problem of finding a minimum such cover r-Tolerant Edge Cover (r-EC) and the problem of finding a maximum minimal such cover Upper r-EC. We present several NP-hardness and inapproximability results for Upper r-EC and for some of its special cases.
https://hal.inria.fr/hal-03165379
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Wednesday, March 10, 2021 - 4:05:05 PM
Last modification on : Tuesday, January 25, 2022 - 8:30:03 AM
Long-term archiving on: : Friday, June 11, 2021 - 7:06:19 PM
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Wednesday, March 10, 2021 - 4:05:05 PM
Last modification on : Tuesday, January 25, 2022 - 8:30:03 AM
Long-term archiving on: : Friday, June 11, 2021 - 7:06:19 PM
Licence
Distributed under a Creative Commons Attribution 4.0 International License