Thumbnail

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

Harutyunyan, Ararat; Khosravian Ghadikolaei, Mehdi; Melissinos, Nikolaos; Monnot, Jérôme; Pagourtzis, Aris (2020), On the Complexity of the Upper r-Tolerant Edge Cover Problem, in Barbosa, Luís S.; Abam, Mohammad Ali, Topics in Theoretical Computer Science, Springer, p. 32-47. 10.1007/978-3-030-57852-7_3

View/Open
Type
Communication / Conférence
Date
2020
Conference title
Third IFIP WG 1.8 International Conference, TTCS 2020
Conference date
2020-07
Conference city
Tehran
Conference country
"Iran
Book title
Topics in Theoretical Computer Science
Book author
Barbosa, Luís S.; Abam, Mohammad Ali
Publisher
Springer
ISBN
978-3-030-57851-0
Number of pages
117
Pages
32-47
Publication identifier
Metadata
Show full item record
Author(s)
Harutyunyan, Ararat
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Khosravian Ghadikolaei, Mehdi
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Melissinos, Nikolaos
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monnot, Jérôme
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Pagourtzis, Aris
Abstract (EN)
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.
Subjects / Keywords
Upper edge cover; Matching; NP-completeness; Approximability