Linear-time graph distance and diameter approximation

doi:10.1111/itor.12236

Linear-time graph distance and diameter approximation

2015-11-30

2

OA

AI

R

Raphael C. S. Machado *

C

Celina M.H. de Figueiredo

DOI：10.1111/itor.12236

原文链接

查看原文

摘要

En 中文

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.

Keyword:

graph diameter

distance in graphs

breadth first search

linear-time algorithm

Linear-time graph distance and diameter approximation

摘要

AI总结

期刊

机构

引用论文