Maintenance of 2- and 3-Connected Components of Graphs, Part 2: 2- and 3-Edge-Connected Components and 2-Vertex-Connected Components.

摘要

In the paper data structures and algorithms are presented to efficiently maintain the 2- and 3-edge-connected components and the 2-vertex-connected components of a graph, under insertions of edges in the graph. At any moment, the data structure can answer the following type of query: given two nodes in the graph, are these nodes 2- or 3-edge-connected or 2-vertex-connected. Starting from an 'empty' graph of n nodes, the algorithms run in O(n+m.alpha(m,n)) time, where m is the total number of queries and edge insertions. The data structure allows for insertions of nodes also. Besides, a linear time algorithm is presented for maintaining the 2-edge-connected components in case the initial graph is connected.