Real-Time Monitoring of Undirected Networks: Articulation Points, Bridges, and Connected and Biconnected Components

Details Real-Time Monitoring of Undirected Networks: Articulation Points, Bridges, and Connected and Biconnected Components Real-Time Monitoring of Undirected Networks: Articulation Points, Bridges, and Connected and Biconnected Components

2012-02-01

arxiv.org/abs/1202.0319v1

Computer Science

Data Structures and Algorithms

Scientific paper

In this paper we present the first algorithm in the streaming model to characterize completely the biconnectivity properties of undirected networks: articulation points, bridges, and connected and biconnected components. The motivation of our work was the development of a real-time algorithm to monitor the connectivity of the Autonomous Systems (AS) Network, but the solution provided is general enough to be applied to any network. The network structure is represented by a graph, and the algorithm is analyzed in the datastream framework. Here, as in the \emph{on-line} model, the input graph is revealed one item (i.e., graph edge) after the other, in an on-line fashion; but, if compared to traditional on-line computation, there are stricter requirements for both memory occupation and per item processing time. Our algorithm works by properly updating a forest over the graph nodes. All the graph (bi)connectivity properties are stored in this forest. We prove the correctness of the algorithm, together with its space ($O(n\,\log n)$, with $n$ being the number of nodes in the graph) and time bounds. We also present the results of a brief experimental evaluation against real-world graphs, including many samples of the AS network, ranging from medium to massive size. These preliminary experimental results confirm the effectiveness of our approach.

Affiliated with

Also associated with

No associations

Rating

Real-Time Monitoring of Undirected Networks: Articulation Points, Bridges, and Connected and Biconnected Components does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Real-Time Monitoring of Undirected Networks: Articulation Points, Bridges, and Connected and Biconnected Components, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Real-Time Monitoring of Undirected Networks: Articulation Points, Bridges, and Connected and Biconnected Components will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-186534