Graph traversals implemented by iterative methods for solving systems of linear equations | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2025. № 68. DOI: 10.17223/20710410/68/5

Graph traversals, such as depth-first search and breadth-first search, are commonly used to solve many problems on graphs. By implementing a graph traversal, we consequently reach all graph vertices that belong to a connected component. The breadth-first search is the usual choice when constructing efficient algorithms for finding connected components of a graph. Methods of simple iteration for solving systems of linear equations with modified graph adjacency matrices can be considered as graph traversal algorithms if we use a properly specified right-hand side. These traversal algorithms, generally speaking, turn out to be neither equivalent to depth-first search nor to breadth-first search. An example of such a traversal algorithm is the one associated with the Gauss - Seidel method. For an arbitrary connected graph, the algorithm requires no more iterations to visit all its vertices than it takes for breadth-first search. For a large number of instances of the problem, fewer iterations will be required.
Download file
Counter downloads: 4
  • Title Graph traversals implemented by iterative methods for solving systems of linear equations
  • Headline Graph traversals implemented by iterative methods for solving systems of linear equations
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 68
  • Date:
  • DOI 10.17223/20710410/68/5
Keywords
graph traversals, connectivity problems on graphs
Authors
References
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.
 Graph traversals implemented by iterative methods for solving systems of linear equations | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2025. № 68. DOI: 10.17223/20710410/68/5
Graph traversals implemented by iterative methods for solving systems of linear equations | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2025. № 68. DOI: 10.17223/20710410/68/5
Download full-text version
Counter downloads: 68