Почему важно учитывать степень вершин при анализе графовых алгоритмов?

Учёт степени вершин при анализе графовых алгоритмов важен по нескольким причинам:

• Балансировка параллельной нагрузки. 15 Если обработка списков рёбер различных вершин графа осуществляется параллельно различными вычислительными устройствами, могут возникать задержки из-за простоя нитей, выделенных для обработки вершин с небольшой степенью, в то время как нити, выделенные для обработки вершин с большой степенью, ещё не завершили свою работу. 5 Разбиение вершин на группы по степени позволяет производить эффективную балансировку параллельной нагрузки, выделяя на обработку вершин различных групп разные вычислительные мощности. 1
• Эффективная реализация алгоритмических абстракций. 1 Для эффективной реализации выделенных алгоритмических абстракций реализация подмножества вершин автоматически должна отслеживать количество вершин, помещённых в данное подмножество, одновременно не позволяя поместить в подмножество вершины с дублирующимися номерами. 1
• Оптимизация работы с памятью. 5 Косвенные обращения к памяти, неизбежно возникающие при запросах о состоянии вершин графа, являются одним из главных факторов, снижающих производительность графовых алгоритмов на современных вычислительных архитектурах. 5 Хранение в смежных участках памяти информации о наиболее часто запрашиваемых вершинах графа (обычно с самой высокой степенью) позволяет решить эту проблему. 5