Графовые классы, для которых диаметр может быть вычислен за линейное время

Напомним, диаметр графа является длина самой длинной кратчайшему пути в . Для данного графа очевидный алгоритм вычисления решает проблему кратчайшего пути всех пар (APSP) и возвращает длину самого длинного найденного пути.G диам ( G $G$$G$$\text{diam}(G)$

Известно, что задача APSP может быть решена за оптимальное время для нескольких классов графов. Для общих графов существует теоретический подход алгебраического графа, работающий за время , где является границей умножения матриц. Однако вычисление диаметра, по-видимому, не является критически связанным с APSP, как показал Юстер .O ( M ( n ) log n ) M ( n $O(n^2)$$O(M(n) \log n)$$M(n)$

Известны ли некоторые нетривиальные классы графов, для которых диаметр можно вычислить еще быстрее, скажем, за линейное время?

Меня особенно интересуют хордовые графы и любые подклассы хордовых графов, такие как блочные графы. Например, я думаю, что диаметр хордового графа можно вычислить за времени, если однозначно представим в виде дерева клик. Такой график также известен как ur-chordal .О ( п + т ) $G$$O(n+m)$$G$

Эксцентриситет вершины - это длина самого длинного кратчайшего пути, начиная с . Диаметр - это максимальный эксцентриситет по всем вершинам. Любая BFS из вершины установит ее эксцентриситет. Поэтому ключевой идеей эффективного нахождения диаметра является предварительная обработка графа для нахождения небольшого набора вершин, по крайней мере одна из которых достигает максимальной эксцентриситета.$v$$v$

Выполняя лексикографический поиск в ширину , конечная вершина часто имеет высокий эксцентриситет. В частности, он гарантированно имеет эксцентриситет не более чем на один диаметр меньше для хордовых графов. Для некоторых подклассов хордовых графов, таких как интервальные графы , гарантируется максимальный эксцентриситет. Это также справедливо для некоторых нехордальных классов, таких как -безопасные графы.$\{\text{AT},\text{claw}\}$

LBFS и BFS являются линейными по размеру графика, но, конечно, если (например, ), тогда время выполнения не будет . Ваше обсуждение подразумевает, что вы, вероятно, действительно хотите линейный алгоритм а не .$m = \Omega(n^2)$$K_n$$o(n^2)$$O(m+n)$$o(n^2)$

Поэтому для некоторых подклассов хордовых графов линейный алгоритм состоит в том, чтобы запустить LBFS, взять конечную вершину, а затем запустить BFS, начиная с этой вершины. Для хордовых графов это определит диаметр с погрешностью не более 1. Графики, для которых это точно, кажутся теми, где четные степени являются хордальными. Это именно те хордальные графы, которые не содержат восходящего солнца или подграфа, сохраняющего расстояния.$(\text{rising sun}- K_2)$

_{(источник: graphclasses.org )}

• Федор Ф. Драган, Фальк Николай и Андреас Брандштадт , LexBFS-упорядочения и степени графов , WG 1996, LNCS 1197, 166–180. doi: 10.1007 / 3-540-62559-3_15

Я не знаю, можно ли это расширить, чтобы точно рассчитать диаметр для всех хордовых графов. Исследование Корнейла, кажется, показывает, что это все еще было открыто в 2004 году. Я также не знаю, был ли проведен анализ по расширению поиска от одной вершины до небольшого постоянного числа или начальных вершин; это может быть интересно исследовать.$\log n$

• Дерек Дж. Корнейл, Лексикографический поиск в ширину - обзор , WG 2004, LNCS 3353, 1–19. doi: 10.1007 / 978-3-540-30559-0_1

Упомянутые блок-графики в вопросе являются наследственно-удаленными. Линейный алгоритм времени для вычисления диаметра для наследственно-дальних графов приведен в [1] (см. Теорему 5).

[1] Драган, Федор Ф. Доминирующие клики в дистанционно-наследственных графах. Springer Berlin Heidelberg, 1994.