Linear‐time graph distance and diameter approximation. (30th November 2015)

• Record Type: Journal Article
• Authors: Machado, Raphael C.S.; de Figueiredo, Celina M.H.
• Other Names: Lavor Carlile guestEditor.; Firer Marcelo guestEditor.; Martínez José Mario guestEditor.; Liberti Leo guestEditor.
• Is Part Of: International transactions in operational research. Volume 23:Number 5(2016:Sep.)
• Page Start: 843
• Page End: 851
• Publication Date: 2015-11-30
• Subjects: graph diameter -- distance in graphs -- breadth first search -- linear‐time algorithm; Operations research -- Periodicals; 003
• DOI: 10.1111/itor.12236
• Languages: English
• ISSNs: 0969-6016

Abstract

Abstract: In this study, we consider the problem of estimating the diameter of a graph, that is, the maximum distance between any two vertices, in linear time. We address a question posed in the literature—whether there exists an interesting graph class with arbitrarily large cycles for which breadth first search (BFS) would always return high‐eccentricity vertices. We answer this question positively, defining a class of graphs that generalizes AT‐free graphs and has no bound on the size of induced cycles, yet BFS always returns a vertex whose eccentricity is within a constant difference from the diameter. In addition, we consider the question—also explicitly stated in the literature—whether some variant of the so‐called multisweep algorithm would always return a high‐eccentricity vertex. We show that the answer is negative by describing a family of graphs for which no variant of multisweep BFS can return a vertex of eccentricity higher than half of the diameter plus a constant.