Как было выяснено раньше, эффективный обход разреженного графа во внешней памяти представляет собой сложную задачу. Действительно, для каждой посещаемой вершины приходится читать с диска список выходящих из нее ребер, что неизбежно влечет за собой хотя бы одну операцию ввода-вывода. Тем самым, суммарно любой стандартный метод потребует не менее V таковых операций. Мельхорну и Мейеру удалось ускорить алгоритм, разбив граф на части и рассматривая множество ребер в тех частях, которые в настоящий момент задевает «фронт волны BFS». Данный прием носит название «hotlist», он был подробно разобран и проанализирован на занятии спецкурса.
Кроме того было начато изучение алгоритмов построения минимальных остовных деревьев и связных компонент во внешней памяти. Подобные алгоритмы используют последовательные стягивания графа и являются модификацией известного метода Борувки. Впрочем, для того, чтобы сделать такой подход эффективным, нужно приложить дополнительные усилия.
Видео
На спецсеминаре состоялось продолжение доклада Ивана Пузыревского про динамическую задачу транзитивного замыкания графа.
Видео
cotass 