Open AccessOn the Minimum Eccentricity Isometric Cycle Problem
Author(s) -
Étienne Birmelé,
Fabien de Montgolfier,
Léo Planche
Publication year - 2019
Publication title -
electronic notes in theoretical computer science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.242
H-Index - 60
ISSN - 1571-0661
DOI - 10.1016/j.entcs.2019.08.015
Subject(s) - isometric exercise , eccentricity (behavior) , mathematics , graph , combinatorics , computer science , physical therapy , medicine , political science , law
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom