On the Minimum Eccentricity Isometric Cycle Problem - Archive ouverte HAL Access content directly
Journal Articles Electronic Notes in Theoretical Computer Science Year : 2019

On the Minimum Eccentricity Isometric Cycle Problem

(1) , (2, 3) , (1, 3)
1
2
3

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.
Fichier principal
Vignette du fichier
ArticleIso.pdf (331.79 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02430756 , version 1 (07-01-2020)

Identifiers

Cite

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⟩
39 View
81 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More