.png){kind=icon}
Return
Linear-time graph distance and diameter approximation
.png){kind=icon}
OA
AI
DOI：10.1111/itor.12236.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
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.
Keywords:
graph diameter
distance in graphs
breadth first search
linear-time algorithm
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
2.9
Papers:
1.8K
Citations:
3.7K
Organization
.png){kind=icon}
