A partition-based computation method for reachability matrix of undirected graphs

In the computation methods of a graph’s reachability matrix, the Warshall algorithm exhibits significant limitations when applied to complex networks with frequently changing topological structures. The paper “A Subgraph Boundary Equivalence Algorithm for Reachability Matrix of Undirected Graphs” introduced a method for rapid computation of reachability matrix, but it is not suitable for scenarios involving multiple partitions. This paper proposes a partition-based computation method built upon the subgraph boundary equivalence algorithm, which accelerates topological analysis for undirected graphs while expanding the algorithm's applicability. The core strategy is to divide the undirected graph into several partitions and compute the reachability matrix for each partition individually, rather than for the entire graph. This approach improves computational efficiency and reduces algorithm execution time. A case study within the paper verifies the correctness and effectiveness of the proposed method.