Skip to Main content Skip to Navigation
Journal articles

On the Minimum Eccentricity Isometric Cycle Problem

Abstract : In this paper we investigate the Minimum Eccentricity Isometric Cycle (MEIC) problem. Given a graph, this problem consists in finding an isometric cycle with smallest possible eccentricity k. We show that this problem is NP-Hard and we propose a 3-approximation algorithm running in O(n(m + kn)) time.
Document type :
Journal articles
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/hal-02430756
Contributor : Fabien de Montgolfier Connect in order to contact the contributor
Submitted on : Tuesday, January 7, 2020 - 3:06:39 PM
Last modification on : Tuesday, January 11, 2022 - 11:16:04 AM

File

ArticleIso.pdf
Files produced by the author(s)

Identifiers

Citation

Etienne Birmele, Fabien de Montgolfier, Léo Planche. On the Minimum Eccentricity Isometric Cycle Problem. Electronic Notes in Theoretical Computer Science, Elsevier, 2019, 346, pp.159-169. ⟨10.1016/j.entcs.2019.08.015⟩. ⟨hal-02430756⟩

Share

Metrics

Les métriques sont temporairement indisponibles