Алгоритмы на графах во внешней памяти

Алгоритмы на графах (построенные в предположении, что граф достаточно мал, чтобы его описание помещалось в оперативной памяти) представляют собой один из наиболее подробно изученных разделов computer science. С ростом объема графа, однако, эти методы перестают быть применимы, т.к. внешняя память (например диск) обладает существенно иным соотношением времени доступа и пропускной способности. В докладе будет дан обзор известных методов работы с графами в модели внешней памяти, показаны типичные трудности, возникающие при адаптации классических алгоритмов, а также сформулирован ряд открытых вопросов.