On the Minimum Eccentricity Isometric Cycle Problem

Etienne Birmele (1) , Fabien de Montgolfier (2, 3) , Léo Planche (1, 3)

1 MAP5 - UMR 8145 - Mathématiques Appliquées Paris 5
2 GANG - Networks, Graphs and Algorithms
3 IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale

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.

Mots clés: k-domination; k-covering; Isometric cycle; Eccentricity

Domaines: Algorithme et structure de données [cs.DS]

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