HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
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.
Document type :
Conference papers
Complete list of metadata

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

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2023-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Ararat Harutyunyan, Mehdi Ghadikolaei, Nikolaos Melissinos, Jérôme Monnot, Aris Pagourtzis. On the Complexity of the Upper r-Tolerant Edge Cover Problem. 3rd International Conference on Topics in Theoretical Computer Science (TTCS), Jul 2020, Tehran, Iran. pp.32-47, ⟨10.1007/978-3-030-57852-7_3⟩. ⟨hal-03165379⟩

Share

Metrics

Record views

57