Algorithmen auf Graphen

Lecturers:Fischer, I.; Meinl, T.
Coverage:4 SWS
Dates & location:
  • Monday, 10:00 - 12:00, 05.150
  • Wednesday, 10:00 - 12:00, 05.150
Audience:WF CE-MA (5.-9. Semester)
WF INF-DH-PS (5.-9. Semester)


Die Veranstaltung ist geeignet für Studierende im Hauptstudium.


(benoteter) Schein, Hauptdiplomprüfung Algorithmische Sprachen


  • Robert Sedgewick: "Algorithms in [C|C++|Java], Part 5 - Graph Algorithms"
  • Claude Berge: "Hypergraphs". North-Holland Mathematical Library, 1993.
  • Annegret Habel: "Hyperedge Replacement". Springer Verlag, Lecture Nodes in Computer Science 643, 1992.
  • Giorgio Gallo, Giustiono Longo, Sang Ngyen, Stefano Pallotina: "Directed Hypergraphs and Applications". Discrete Applied Mathematics 42, S. 177-201, 2003.
  • Scott Fortin: "The Graph Isomorphism Problem"
  • J. R. Ullmann: "An Algorithm for Subgraph Isomorphism"
  • Brendan McKay: "Practical Graph Isomorphism"
  • Noah Giansiracusa: "Determinig Graph Isomorphism via Canonical Labeling"
  • Christian Borgelt, Michael R. Berthold: "Mining Molecular Fragments: Finding Relevant Substructures of Molecules"
  • Heiko Hofer, Christian Borgelt, Michael R. Berthold: "Large Scale Mining of Molecular Fragments with Wildcards"
  • Xifeng Yan, Jiawei Han: "gSpan: Graph-Based Substructure Pattern Mining"
  • Jun Huan, Wei Wang, Jan Prins: "Efficient Mining of Frequent Subgraph in the Presence of Isomorphism"
  • H. Bunke, P. Foggia, C. Guidobaldi, C. Sansone, M. Vento: "A comparison of algorithms for maximum common subgraph on randomly connected graphs"
  • Automatisches Zeichnen von Graphen, Vorlesung Uni Köln
  • Graph Drawing - Algorithms for the Visualiation of Graphs. Giuseppe di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis, Prentice Hall, ISBN 0-13-301615-3, 1999.
  • Graphgrammatik-Vorlesung, Lehrbuch, Einführung von Prof.Schneider
  • Einführung Reiko Heckel, Uni Leicester
  • D. Blostein, A. Schürr, Computing with Graphs and Graph Rewriting, Software - Practice and Experience, Vol. 29, No. 3, Los Alamitos: IEEE Computer Society Press, 1999, 1-21
  • Graph Transformation for Specification and Programming, Marc Andries, Gregor Engels, Annegret Habel, Berthold Hoffmann, Hans-Jörg Kreowski, Sabine Kuske, Detlef Plump, Andy Schürr, Gabriele Taentzer (1996)
  • Summerschool on Graph Transformations
  • G. Rozenberg (Hrsg.): Handbook of Graph Grammars and Computing by Graph Transformation, World Scientific, 1997
  • Roman Morawek: Path Finding for Mobile Software Agents or The Traveling Salesman Problem under Incomplete Information; Dissertation, TU Wien, 2003
  • David. S. Johnson, Lyle A. McGeoch: The Traveling Salesman Problem: A Case Study in Local Optimization; 1995
  • P. Larranaga, C. M. H. Kuijpers, R. H. Murga I. Inza, S. Dizdarevic: Genetic Algorithms for the Traveling Salesman Problem: A Review for Representations and Operators, 1999
  • Brian Hayes: Graph Theory in Practice: Part II; American Scientist, 2000, 88(2)
  • Jurij Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos: Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication; PKDD 2005
watermark seal