Finding connected components of a graph using traversals associated with iterative methods for solving systems of linear equations
<|reference_start|>Finding connected components of a graph using traversals associated with iterative methods for solving systems of linear equations: To solve many problems on graphs, graph traversals are used, the usual variants of which are the depth-first search and the breadth-first search. Implementing a graph traversal we consequently reach all vertices of the graph 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 and with the properly specified right-hand side can be considered as graph traversal algorithms. These traversal algorithms, generally speaking, turn out to be non-equivalent neither to the depth-first search nor the breadth-first search. The example of such a traversal algorithm is the one associated with the Gauss-Seidel method. For an arbitrary connected graph, to visit all its vertices, the algorithm requires not more iterations than that is required for BFS. For a large number of instances of the problem, fewer iterations will be required.<|reference_end|>
@article{prolubnikov2024finding,
    title={Finding connected components of a graph using traversals associated with
  iterative methods for solving systems of linear equations},
    author={A.V. Prolubnikov},
    journal={arXiv preprint arXiv:2407.10790},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.10790},
    primaryClass={cs.DM}
}