Временная сложность центральности между? - PullRequest
Новая
       16

Временная сложность центральности между?

0 голосов
/ 30 июня 2011

Какова временная сложность вычислений межцентровость , если нам дана матрица предшественника кратчайшего пути графа?

Ячейки матрицы предшественника выглядят так:

  • если узел i и узел j напрямую связаны, то значение в ячейке равно 0;
  • , если узел i и узел j не связаны, тогда значение в ячейке равно -1;
  • else cell = предшественник ( j ) - это может быть только один предшественник, если существует один кратчайший путь или массив предшественников, если между * 1022 существует более одного кратчайшего путия и j .

Спасибо за ваш ответ,

Я знаком с алгоритмом Брандеса.Однако алгоритм Брандеса вычислит промежуточность для всех узлов в сети.Я думаю, что время, затрачиваемое на вычисление CB для одной вершины, такое же, как время для вычисления CB для всех вершин, поскольку алгоритм Брандеса не может быть адаптирован для такого случая.

Итак, моя идея заключалась в том, чтобы сохранитьматрица предшественника, и чтобы иметь возможность вычислять CB для определенной вершины (и не нужно ждать всех вершин вычислений CB).Я знаю, что не могу достичь меньшей временной сложности, но я думаю, что разница во времени может быть достигнута, если не вычислить CB для всех 7000 вершин.Вместо этого, имея эту матрицу, я могу вычислить CB только для одной вершины.

Я думаю, что можно вычислить CB в O (n ^ 2 * L), где L - средний кратчайший путь, когда у нас есть матрица предшественника.

Что вы думаете об этой концепции?

1 Ответ

3 голосов
/ 08 июля 2011

Насколько я могу судить, наиболее известным алгоритмом для вычисления центральности промежуточности является тот, который описан в этой статье:

Вы увидите, что этот алгоритм в качестве первого шага вычисляет количество кратчайших путей между каждой парой узлов.Это естественно сделать так, чтобы одновременно вычислялась матрица предшественника.Таким образом, кажется, что нет никакого преимущества в предварительном вычислении матрицы предшественника: вы все равно получаете ее по существу бесплатно при выполнении алгоритма Брандеса.

(Конечно, это не доказательство того, что это не имеет значения,и, может быть, кто-то другой знает лучше. Вы можете спросить на cstheory.stackexchange.com .)

...