Xiaohui Cai

"Efficient Connectivity Algorithms for Small Dense Graphs"

Abstract:

Algorithms for biconnectivity, triconnectivity and k-connectivity are investigated for use in conjunction with graph generation. In this context, the graphs are small (usually fewer than 16 nodes) but dense (roughly half of the possible edges are present). Three linear time algorithms for biconnectivity are compared. The linear time triconnectivity algorithm of Hopcroft and Tarjan is implemented, along with a network flow algorithm for general k-connectivity. Using these algorithms and the makeg utility of nauty, data are obtained on the numbers of labeled and unlabeled graphs by number of nodes, number of edges, and connectivity.