Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00269 Dynamic Graph Clustering Using Minimum-Cut Trees Robert Görke , Tanja Hartmann , and Dorothea Wagner Vol. 16, no. 2, pp. 411-446, 2012. Regular paper Abstract Algorithms or target functions for graph clustering rarely admit quality guarantees or optimal results in general. Based on properties of minimum-cut trees, a clustering algorithm by Flake et al. does however yield such a provable guarantee, which ensures the quality of bottlenecks within the clustering. We show that the structure of minimum s-t-cuts in a graph allows for an efficient dynamic update of those clusterings, and present a dynamic graph clustering algorithm that maintains a clustering fulfilling this quality guarantee, and that effectively avoids changing the clustering. Experiments on real-world dynamic graphs complement our theoretical results.
|
Submitted: September 2010. Accepted: June 2012. Final: July 2012. Published: August 2012. Communicated by Michael Kaufmann |
Journal of Graph Algorithms and Applications |