Prof. Günter M. Ziegler

Blockseminar ``Enumerationsverfahren'' (Sommersemester 2003)

1. Suchbäume (Annika Poerschke, annikapoerschke "at" gmx.de)
   Ausarbeitung
   
   • D. E. Knuth: Estimating the efficiency of backtrack programs,
     Math. Computat. 29 (1975), 121-136.

2. Springer-Touren (So-Young Lee, sooilee "at" gmx.de)
   Ausarbeitung
   
   • M. Löbbing & Wegner: The number of knight's tours equals 33,439,123,484,294 - counting with binary decision diagrams, Electronic J. Combinatorics 3 (1996), R5.
     
   • B. McKay: Knight's tours of an 8 x 8 chessboard, Preprint, 4 pages

3. Die Komplexität des Zählens (Benjamin Hiller, hiller "at" zib.de)
   Ausarbeitung
   
   • M. Jerrum: The computational complexity of counting, Proc. International Congress ofMathematicians (Zürich, 1994), Birkhäuser, Basel 1995, Vol. II, 1407-1416

4. Isomorphie-freies Aufzählen (Thomas Thevis, thevis "at" math.tu-berlin.de)
   Ausarbeitung
   
   • R. C. Read: Every one a winner. How to avoid isomorphism search when cataloguing combinatorial configurations, Annals of Discrete Math. 2 (1978), 107-120
     
   • B. McKay: Isomorph-free exhaustive generation, J. Algorithms26 (1998), 306-324

5. Graphen (Nader Razouk, nrazouk "at" gmx.de)
   Ausarbeitung
   
   • T. Jensen & G. Royle: Small graphs with chromatic number 5:
     A Computer search,  J. Graph Theory 19 (1995), 107-116

6. n-Tupel (Dirk Petzoldt, Dirk.Petzoldt "at" web.de)
   Ausarbeitung
   
   • D. E. Knuth: Generating all n-tuples Ch. 7.2.1.1, prefascicle 2A of "The Art of Computer Programming" (vol. 4), released September 2001, version of November 2002
     http://www-cs-faculty.stanford.edu/~knuth/fasc2a.ps.gz

7. Permutationen (Felix Kälberer, felixk "at" cs.tu-berlin.de)
   Ausarbeitung
   
   • D. E. Knuth: Generating all n-tuples, Ch. 7.2.1.2, prefascicle 2B of "The Art of Computer Programming" (vol. 4), version of November 2002, http://www-cs-faculty.stanford.edu/~knuth/fasc2a.ps.gz

8. Ebene Triangulierungen (Florian Zickfeld, Florian.Zickfeld "at" web.de)
   Ausarbeitung
   
   • G. Brinkmann & B. McKay: plantri A program for generation of certain type of planar graph,
     http://cs.anu.edu.au/people/bdm/plantri
     
   • P. Elango: Triangulations of Spheres and Discs,
     Master's Thesis, University of Malaysia, Kuala Lumpur 2002, 125 pages.

9. Fullerene (Jens Fischer, fischer.jens "at" web.de)
   Ausarbeitung
   
   • G. Brinkmann & A. W. M. Dress: A constructive enumeration of fullerenes, J. Algorithms 23 (1997), 345-358

10. 0/1-Würfel, 0/1-Polytope (Verena Vasak, ena1204 "at" web.de)
    Ausarbeitung
    
    • O. Aichholzer & F. Aurenhammer: Classifying hyperplanes in hypercubes, SIAM J. Discrete Math. 9 (1996), 225-232
      
    • O. Aichholzer: Extremal properties of 0/1-polytopes of dimension 5, in: "Polytopes - Combinatorics and Computation" (G. Kalai and G. M. Ziegler, eds.), DMV Seminars 29, Birkhäuser-Verlag, Basel 2000, 111-130

11. Gitter-Triangulierungen Wie viele Gitter hat ein 6x6-Gitter? (Juliane Dunkel, juliane_dunkel "at" web.de)
    Ausarbeitung
    
    • V. Kaibel & G. M. Ziegler: Counting lattice triangulations,
      Preprint, TU Berlin, November 2002, 27 pages; to appear in British Combinatorial Surveys (C. D. Wensley, ed.), Cambridge University Press 2003.
      
    • O. Aichholzer: The path of a triangulation, in: Proc. 15th Annual ACM Workshop Computational Geometry (Miami Beach, Florida, June 13-15, 1999) ACM Press 1999, pp. 14-23.