Родионов А.С.
Можно ли добиться дальнейшего ускорения расчёта характристик связности случайного графа?
В докладе рассматриваются новые приёмы ускорения расчёта некоторых характеристик связности случайного графа (вероятность связности подмножества вершин, средняя вероятность парной связности, математическое ожидание размера связного подграфа, содержащего выделенную вершину и некоторые другие). Эти задачи имеют доказанно неполиномиальный характер сложности и, как правило, ищутся приближённые решения. Однако, с развитием вычислительной техники и разработкой параллельных алгоритмов, нахождение точных решений стало возможным для графов достаточно большой размерности для решения практических задач (до сотен вершин в случае небольшой их средней степени). Кроме того, найденные за годы решения этих задач, в том числе автором доклада, различные приёмы редукции и декомпозиции позволили ещё больше поднять размерность рассчитываемых графов. Точные решения необходимы также для оценки качества приближённых алгоритмов.
Предлагаются различные приёмы развития известного метода факторизации, когда вместо рассмотрения одного разрешающего ребра рассматривается некоторое небольшое подмножество специальным образом выбранных рёбер.
К списку докладов