Поиск центра графа Опции

[Tony]

Здравствуйте.

Собственно задача:

Имеется сильно связный неориентированный невзвешенный граф. Требуется найти такую вершину (центр), чтобы кратчайшие расстояния от нее до всех остальных вершин графа были, по-возможности, минимальны.(по-моему не совсем корректно, поэтому скажу иначе: поиск в ширину, пущенный от нее, должен сделать минимальное число "волн").

Естественно, решение за O(n^2) очевидно (просто серия из n поисков в ширину), но при этом время работы алгоритма слишком велико. Собственно, был бы рад любым идеям по реализации данного алгоритма .

ЗЫ
Из собственных мыслей:

1.) Взять произвольную вершину. Пустив bfs из нее, найти наиболее удаленную от нее вершину ( пусть она будет называться L ). Пустив bfs от L, найти наиболее удаленную от нее вершину ( R ). Пустить одноременно два bfs'а от L и R и ждать их пересечения. Центр, имхо, будет лежать где-то в множестве вершин, вошедших в это пересечение. (но опять - таки их слишком много)

2.) Попытаться использовать данные предыдущих поисков. Но эта идея по-моему бесперспективна...

[Tony]

Можно посмотреть на твой граф (хотя бы приблизительно, количество вершин чему равно?).

Количество вершин невелико(порядка тысячи). Дело в том, что время работы ограничено двумя секундами (а при этом имеются еще и некоторые подготовительные операции).

Даже когда известны ВСЕ расстояния между всеми вершинами, возможно ли определить центр по этой матрице расстояний меньше, чем за квадрат?

В том-то и дело, что мне нужно придумать алгоритм, который не будет считать расстояния между всеми вершинами.

Вообще, мне кажется, из того, что граф неориентированный и невзвешенный вытекает то, что значения минимального эксцентриситета для двух смежных вершин не будут различаться больше, чем на единицу. Исходя из этих соображений, я написал поиск, который, начиная с какой-то случайной вершины, идет по смежным вершинам с минимальным эксцентриситетом подобно поиску в глубину(причем я обрываю его по достижениии какого-то предельного числа ходов). Но опять-же при заданных временных ограничениях он не находит правильного ответа. Почему так происходит, я не понимаю (предельное число ходов - около 800, при этом, имхо, можно несколько раз пересечь граф по диаметру).