МОЖНО ЛИ ДОБИТЬСЯ ДАЛЬНЕЙШЕГО УСКОРЕНИЯ РАСЧЕТА ХАРАКТЕРИСТИК СВЯЗНОСТИ СЛУЧАЙНОГО ГРАФА?

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

Предлагаются различные приемы развития известного метода факторизации, когда вместо рассмотрения одного разрешающего ребра рассматривается некоторое небольшое подмножество специальным образом выбранных ребер.

Исследования выполнены в рамках государственного задания ИВМиМГ СО РАН (0251-2021-0005).
Статья по докладу на XVIII Международной Азиатской школе-семинаре «Проблемы оптимизации сложных систем», Киргизия, Иссык-Куль, 20.07.2022-30.07.2022.