|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
О методе ускорения поиска кратчайших путей на основе удаления вершин малых степенейдоклад на конференции
- Автор: Зизов В.С.
- Всероссийская с международным участием Конференция : Конференция «Программирование и вычислительная математика», посвящённая 100-летнему юбилею со дня рождения Николая Павловича Трифонова
- Даты проведения конференции: 3 декабря 2025
- Дата доклада: 3 декабря 2025
- Тип доклада: Устный
- Докладчик: Зизов В.С.
- Место проведения: Факультет ВМК МГУ им. М.В.Ломоносова, Россия
-
Аннотация доклада:
В работе предлагается новый метод ускоренного поиска кратчайших путей в разреженных ориентированных взвешенных графах, Lace-graph compression (LGC). Метод сочетает последовательное удаление вершин с малой степенью с построением программы переходов для сохранения корректности путей. Он не требует планарности или строгой структуры графа. Результаты экспериментов демонстрируют значительное ускорение по сравнению с алгоритмом Дейкстры.
- Доклад на конференции выполнен в рамках проекта (проектов):
- Добавил в систему: Зизов Вадим Сергеевич