Skip to Main content Skip to Navigation
Conference papers

On the Complexity of the Upper r-Tolerant Edge Cover Problem

Ararat Harutyunyan 1 Mehdi Ghadikolaei 1 Nikolaos Melissinos 1 Jérôme Monnot 1 Aris Pagourtzis 2
1 LAMSADE - Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision
2 NTUA - National Technical University of Athens [Athens]
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.
Keywords : Upper edge cover Matching NP-completeness Approximability
Document type :
Conference papers
Complete list of metadata
https://hal.inria.fr/hal-03165379
Contributor : Hal Ifip <>
Submitted on : Wednesday, March 10, 2021 - 4:05:05 PM
Last modification on : Thursday, March 11, 2021 - 3:35:31 AM

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

Collections

IFIP | IFIP-LNCS | IFIP-LNCS-12281 | IFIP-TC1 | IFIP-TC | PSL | UNIV-DAUPHINE | CNRS | LAMSADE-DAUPHINE

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

8

 

Contact                    Legal Notice                    Personal Data