ГлавнаяАрхивИспользование особенностей взвешенных графовдля более быстрого определения их характеристик

Использование особенностей взвешенных графовдля более быстрого определения их характеристик | Прикладная дискретная математика. 2012. № 2(16).

Предлагаются алгоритмы быстрого поиска центра, радиуса и диаметра взвешенного графа по матрице кратчайших расстояний, использующие особенности графов реальных дорожных сетей, и приводятся результаты сравнительной оценки алгоритмов с поиском характеристик простым проходом по матрице.
  • Title Использование особенностей взвешенных графовдля более быстрого определения их характеристик
  • Headline Использование особенностей взвешенных графовдля более быстрого определения их характеристик
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 2(16)
  • Date:
  • DOI
Ключевые слова
центр графа, радиус графа, диаметр графа, матрица кратчайших расстояний, взвешенный граф, graph center, graph radius, graph diameter, all-pairs shortest path matrix, graph features, weighted graph
Авторы
Ссылки
Zwick U. and Shoshan A. All pairs shortest paths in undirected graphs with integer weights // Proc. of the 40th IEEE Symposium on Foundations of Computer Science. Washington: IEEE Computer Society Washington, 1999. P. 605-614.
Galil Z. and Margalit O. All pairs shortest distances for graphs with small integer length edges // Information and Computation. 1977. No. 134. P. 103-139.
Johnson D. B. Efficient algorithms for shortest paths in sparse graph // J. ACM. 1977. No. 24. P. 1-13.
Использование особенностей взвешенных графовдля более быстрого определения их характеристик | Прикладная дискретная математика. 2012. № 2(16).
Использование особенностей взвешенных графовдля более быстрого определения их характеристик | Прикладная дискретная математика. 2012. № 2(16).
Полнотекстовая версия