Algorithm of the day

[antilamer]

Почитал немного just for fun про то, как вычислять в больших графах достижимость; некоторые идеи очень понравились.

Постановка задачи: Есть очень большой граф (миллионы-миллиарды вершин и рёбер); надо научиться быстро отвечать на вопросы

Comments

[major_m]

Да, Ракеш Агравал всегда хорош. =)

Я верно понимаю, что в Interval Labeling после того, как посчитали intervals(A) из него еще надо выкинуть все интервалы, которые попали в [iIn_A, iOut_A]?

[antilamer]

Нет, почему? Ничего специально выкидывать не надо, просто в каждом union надо удалять лишние интервалы.

[major_m]

Это и будут лишние интервалы -- интервалы, соответствующие детям в остовном дереве.

[ex_juan_gan]

А алгоритмы маршрутизации? Типа двустороннего Дийстры, ну и там, говорят, уже куда получше есть.

[antilamer]

Последняя ссылка - как раз state of the art. Еще офигенная штука - contraction hierarchies.

[darnley]

Жека, спасибо! Люблю такое!!