Institute of Theoretical Informatics, Algorithmics

State of the Art

Among other things our previous work in this field encompasses the following publications.


  • U. Brandes, M. Gaertler, D. Wagner. Engineering Graph Clustering: Models and Experimental Evaluation. ACM Journal of Experimental Algorithmics, 12(1.1):1-26, 2007.
  • U. Brandes, D. Delling, M. Gaertler, R. Görke, M. Hoefer, Z. Nikoloski, D. Wagner. On Modularity Clustering. IEEE Transactions on Knowledge and Data Engineering, to appear.
  • M. Gaertler, R. Görke, D. Wagner and S. Wagner. How to Cluster an Evolving Graph. In: Proc. European Conference on Complex Systems (ECCS'06), Oxford, England, 25-29 September 2006.
  • M. Gaertler, R. Görke, D. Wagner. Significance-Driven Graph Clustering. In: Proceedings of The Third International Conference on Algorithmic Aspects in Information and Management (AAIM), pages 11-26, Portland, USA, 6-8 June 2007.
  • D. Delling. Analyse und Evaluierung von Vergleichsmaßen für Graphclusterungen. Diplomarbeit, Institut für Theoretische Informatik - Universität Karlsruhe (TH), February 2006.
  • D. Delling, M. Gaertler, D. Wagner. Generating Significant Graph Clusterings. In: Proceedings of the European Conference of Complex Systems (ECCS'06), September 2006.
  • U. Brandes, S. Cornelsen, C. Fiess, and D. Wagner. How to draw the minimum cuts of a planar graph. Computational Geometry: Theory and Applications, 29:117–133, 2004. Available online at
  • U. Brandes, S. Cornelsen, and D. Wagner. Characterizing families of cuts that can be represented by axis-parallel rectangles. Journal of Graph Algorithms and Applications, 9(1):99–115, 2005.
  • S. Cornelsen, Y. Dinitz, and D. Wagner. Planarity of the two-level cactus representation. In Proceedings of the 27th Workshop on Graph-Theoretic Concepts in Computer Science (WG’01), volume 2204 of Lecture Notes in Computer Science, pages 91–102. Springer-Verlag, 2001.
  • M. Gaertler. Clustering. In Brandes and Erlebach [11], pages 178–215.
  • M. Gaertler. Algorithmic Aspects of Clustering – Theory, Experimental Evaluation, and Applications in Network Analysis and Visualization. Dissertation, Universität Karlsruhe (TH), 2007. submitted Dezember 2006.
  • M. Holzer, G. Prasinos, F. Schulz, D. Wagner, and C. D. Zaroliagis. Engineering planar separator algorithms. In Proceedings of the 13th Annual European Symposium on Algorithms (ESA’05), volume 3669 of Lecture Notes in Computer Science, pages 628–639. Springer, 2005.
  • M. Holzer, F. Schulz, and D. Wagner. Engineering Multi-Level Overlay Graphs for Shortest-Path Queries. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX 2006), volume 129 of Proceedings in Applied Mathematics, pages 156–170. SIAM, January 2006.
  • J. Speck. Clustern mit beschränkter Clustergröße, Studienarbeit, Institut für Theoretische Informatik, Universität Karlsruhe (TH), Dezember 2006.
  • S. Wagner and D. Wagner. Comparing Clusterings – An Overview. Technical Report 2006-04, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2006.