ГлавнаяАрхивОбходы графов, реализуемые итерационными методами решения систем линейных уравнений

Обходы графов, реализуемые итерационными методами решения систем линейных уравнений | Прикладная дискретная математика. 2025. № 68. DOI: 10.17223/20710410/68/5

Обходы графов используются для решения многих задач. Обычные варианты обхода графа - это поиск в глубину и в ширину. При обходе связного графа последовательно достигаются все его вершины в результате переходов по рёбрам. Поиск в ширину - обычный выбор при построении эффективных алгоритмов нахождения компонент связности графа. Методы простой итерации для решения систем линейных алгебраических уравнений с модифицированными матрицами смежности графов и заданной правой частью могут быть рассмотрены как алгоритмы обхода графа. Эти алгоритмы дают обходы, вообще говоря, отличные от обходов графа в глубину и в ширину. Примером такого алгоритма является алгоритм обхода графа, который даёт метод Гаусса - Зейделя. Для произвольного связного графа этому алгоритму требуется количество итераций не большее, чем для обхода в ширину. Для большого количества индивидуальных задач достаточно меньшего числа итераций.
  • Title Обходы графов, реализуемые итерационными методами решения систем линейных уравнений
  • Headline Обходы графов, реализуемые итерационными методами решения систем линейных уравнений
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 68
  • Date:
  • DOI 10.17223/20710410/68/5
Ключевые слова
обходы графов, задачи о связности на графах
Авторы
Ссылки
Cormen T.H., Leiserson С. Е., Rivest R.L., and Stein С. Introduction to Algorithms (3rd ed). MIT Press, 2009.
Zuse K. Der Plankalkiil. Konrad Zuse Internet Archive. 1972. S. 96-105.
Moore E. F. The shortest path through a maze // Proc.Intern. Svmp. Theory of Switching. P. II. Cambridge, MA: Harvard University Press, 1959. P. 285-292.
Lee C. Y. An algorithm for path connections and its applications // IRE Trans. Electronic Comput. 1961. V. EC-10. No.3. P.346-365.
Вearner S., Asanovic K., and Patterson D. Direction-optimized breadth-first search // Proc. SCT2. Salt Lake City, Utah, 2012. Article 12. P. 1-10.
Biicker H. M. and Sohr C. Reformulating a breadth-first search algorithm on an undirected graph in the language of linear algebra // Proc. MCSI'14. IEEE Computer Society, 2014. P. 33-35.
Azad A. and Bulug A. A work-efficient parallel sparse matrix-sparse vector multiplication algorithm // Proc. IPDPST7. Orlando, Florida, USA, 2017. P.688-697.
Yang C., Bulug A., and Owens J. D. Graphblast: A high-performance linear algebra-based graph framework on the GPU // ACM Trans. Math. Software. 2022. V.48 (1). P. 1-51.
Yang C., Wang Y., and Owens J. D. Fast sparse matrix and sparse vector multiplication algorithm on the GPU // Proc. IPDPSW'15. IEEE Computer Society, 2015. P.841-847.
Burkhardt P. Optimal algebraic Breadth-First Search for sparse graphs // ACM Trans. Knowl. Discov. Data. 2021. V. 15 (5). Article 77.
Пролубников А. В. Сведение задачи проверки изоморфизма графов к задаче проверки равенства полиномов от n переменных // Тр. ИММ УрО РАН. 2016. Т. 22. №1. С.235-240.
Пролубников А. В. Точность и сложность вычислений, необходимые для проверки изоморфизма графов сравнением полиномов // Вычислительные технологии. 2016. Т. 21. №6. С. 71-88.
Обходы графов, реализуемые итерационными методами решения систем линейных уравнений | Прикладная дискретная математика. 2025. № 68. DOI: 10.17223/20710410/68/5
Обходы графов, реализуемые итерационными методами решения систем линейных уравнений | Прикладная дискретная математика. 2025. № 68. DOI: 10.17223/20710410/68/5