Determining the connectedness of an undirected graph is a frequent issue in practical graph mining and regarded as a key subproblem of the graph partitioning problem. Apart from graph partitioning, graph connectedness also plays an imperative role in tracking the spread of disease, VLSI design, social network analysis, and theoretical studies in graph theory such as "Cayley graph". This work reviews several important methods for determining the connectedness of an undirected graph, such as breadth-first search, depth-first search, and the eigenvalues of a graph Laplacian matrix. In addition, we propose several new methods, such as power sum and logical sum of adjacency matrix. We compare all the relevant methods empirically on random graphs with up to 10 000 vertices, and show that the breadth-first search and logical sum methods deliver good performances on large graphs with more than 100 vertices and the logical sum method is the fastest.
TAN Tunzi
,
GAO Suixiang
,
YANG Wenguo
. Determining the connectedness of an undirected graph[J]. Journal of University of Chinese Academy of Sciences, 2018
, 35(5)
: 582
-588
.
DOI: 10.7523/j.issn.2095-6134.2018.05.002
[1] Alan G. Algorithmic graph theory[J]. Oberwolfach Reports, 1989, 3(1):379-460.
[2] Douglas B W. Introduction to graph theory[M]. 2nd ed. Upper Saddle River:Prentice hall, 2001.
[3] Robert S, Kevin W. Algorithms[M]. 4th ed. Boston:Addison-Wesley Professional, 2011.
[4] Santanu S R. Graph theory with algorithms and its applications:in applied science and technology[M]. India:Springer, 2013.
[5] Lorenzo B, Michele C, Giovanni R. A Branch-and-cut algorithm for the Equicut problem[J]. Mathematical Programming, 1997, 78(2):243-263.
[6] John E M. Branch and cut for the k-way Equipartition Problem[J]. Discrete Optimization, 2007, 4(1):87-102.
[7] Stefan E K, Franz R, Jens C. Solving graph Bisection problems with Semidefinite Programming[J]. INFORMS Journal on Computing, 2000, 12(3):177-191.
[8] Huang A, Zhu W. Connectedness of graphs and its application to connected matroids through covering-based rough sets[J]. Soft Computing, 2016, 20(5):1841-1851.
[9] Andrew B K, Jens L, Igor L M, et al. VLSI physical design:from Born graph partitioning to timing closure[M]. Hamburg:Springer, 2011.
[10] Maria C, Bernard R, Yori Z. Claw-free graphs with strongly perfect complements:fractional and integral version. part I. Basic graphs[J]. Discrete Applied Mathematics, 2011, 159(17):1971-1995.
[11] James A B. Graph theory and social networks:a technical comment on connectedness and connectivity[J]. Sociology, 1969, 3(2):215-232.
[12] Laszlo B. Some applications of graph contractions[J]. Journal of Graph Theory, 1977, 1(2):125-130.
[13] Edward F M. The shortest path through a maze[J]. In proceedings of the International Symposium on the Theory of Switching, 1959:285-292.
[14] Lee C Y. An algorithm for path connections and its applications[J]. IRE Transactions on Electronic Computers, 1961, 3(1):346-365.
[15] Thomas H C, Charles E L, Ronald L R, et al. Introduction to algorithms[M]. 3rd edition. Cambridge:MIT Press, 2001.
[16] Shimon E. Graph algorithms[M]. Cambridge and New York:Cambridge University Press, 2011.
[17] Pearson K. The problem of the random walk[J]. Nature, 1905, 72(1865):294.
[18] Kampen N G. Stochastic processes in physics and chemistry[M]. Revised and enlarged edition. Amsterdam/London/New York/Tokyo:Elsevier, 1992.
[19] Pierre D G. Scaling concepts in polymer physics[M]. Ithaca and London:Cornell University Press, 1979.
[20] Sriram V P, Steven S S. Computational discrete mathematics:combinatorics and graph theory with mathematica[M]. Cambridge:Cambridge University Press, 2009.
[21] Chung F. Spectral graph theory[M]. New York:American Mathematical Society, 1997.
[22] Michael W N. The Laplacian spectrum of graphs[D]. Manitoba:University of Manitoba, 2000.
[23] Li T Y. The Laguerre tteration in solving the symmetric tridiagonal eigenproblem, revisited[J]. SIAM Journal on Scientific Computing, 1994, 15(5):1145-1173.
