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
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


Files produced by the author(s)



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⟩



Les métriques sont temporairement indisponibles