This page contains a semester project I did a while back.
Articulation Point Detection by Michael Verdicchio
Articulation points, or cut-vertices, are vertices in an undirected graph which when deleted disconnect the graph. In other words, they separate the biconnected components of a graph. Their detection is of interest in the context of disrupting network communication, for example, in a gene regulatory network. If a drug is to target a particular gene or gene product, it is tempting to focus on those with maximal degree in the network of interest, but perhaps the genes holding the whole network together, the articulation points, deserve attention as well. This semester project serves to 1) implement an efficient articulation point detection algorithm, and 2) compare its performance against a trivial and inefficient articulation point detection algorithm. As would be expected, the O(|V|+|E|) algorithm performed much better than the trivial O(|V||E|).
Report and Overview of Software (doc | docx | pdf)
Software (jar)
Sample NEATO-formatted graph files (here)
Sample diagnostic output file (here)
Java source files (here)
