|
Abstract : |
In this paper a data structure is presented to efficiently maintain the 2and 3-edge-connected components of a graph, under insertions of edges in the graph. Starting from an "empty " graph of n nodes, the insertion of e edges takes O(nlogn-[- e) time in total. The data structure allows for insertions of nodes also (in the same time bounds, taking n as the final number of nodes). Moreover, at any moment, the data structure can answer the following type of query in O(1) time: given two nodes in the graph, are these nodes 2- or, |
