Seminar Markov Ketten (WS 95/96) Artur Czumaj, Miroslaw Kutylowski, Christian Scheideler

Termine

• 8.12.95, 11:00-12:00, F1.110 (Fürstenallee)
  
  • Christian Scheideler, ``Einführung in Markov Ketten''
  
  
• 1.02.96, 14:20-15:10, F0.231 (Fürstenallee)
  An external talk at Theory Day at the University of Paderborn,
  • Paul Spirakis(Patras)
    ``An RNC scheme for approximating the permanent of dense bipartite graphs''
  
  
• 7.03.96, 9:00-11:00, F1.110 (Fürstenallee)
  
  • Artur Czumaj, ``Estimating the Number of k-colorings of a Graph''
  • Christian Scheideler, ``Hamiltonian Paths and Cycles''
  
  
• 14.03.96, 9:00-11:00, F1.110 (Fürstenallee)
  
  • Conrad Berhörster und Michael Ruff, ``Approximating the Permanent''
  
  
• 21.03.96, 9:00-11:00, F1.110 (Fürstenallee)
  
  • Mioslaw Kutylowski, ``Random Graphs and Structures''
  • Klaus Schröder, ``Simulated Annealing''
  
  
• 28.03.96, 10:00-12:00, F1.110 (Fürstenallee)
  Ausweichtermin
  
  
• Zusäzlich wird ein Gastvortrag von M. Dyer am 24.04.96 geplannt.
  
  
  

• Approximating the Permanent
  (Conrad Berhörster (conni@cadlab.de) und Michael Ruff (ruff))
  
  • Literatur:
    • M. Jerrum and A. Sinclair, Approximating the permanent, SIAM Journal on Computing, 18(6):1149-1178, 1989.
  • Ausarbeitung von Conrad Berhörster
  • Ausarbeitung von Michael Ruff
  
  
  
• Hamiltonian Paths and Cycles
  (Christian Scheideler (chrsch))
  
  • Literatur:
    • M. Dyer, A. Frieze, and M. Jerrum, Approximately counting Hamiltonian paths and cycles in dense graphs, Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1994, and Technical Report ECS-LFCS-93-259, Department of Computer Science, University of Edinburgh, April 1993.
    • A. Frieze, M. Jerrum, M. Molloy, R. Robinson, and N. Wormald, Generating and counting Hamilton cycles in random regular graphs, Technical Report ECS-LFCS-94-313, Department of Computer Science, University of Edinburgh, December 1994.
  
  Folien zu den Vortrag (ohne Bilder, unkorrigiert)
  
  
• Random Graphs and Structures
  ( Mioslaw Kutylowski (mirekk))
  
  • Literatur:
    • M. Jerrum and A. Sinclair, Fast uniform generation of regular graphs, Theoretcal Computer Science, 73:91-100, 1990.
    • M. R. Jerrum, L. G. Valiant, and V. V. Vazirani, Random generation of combinatorial structures from a uniform distribution, Theoretcal Computer Science, 43:169-188, 1986.
    • B. D. McKay and N. C. Wormald, Uniform generation of random regular graphs of moderate degree, Journal of Algorithms, 11:52-67, 1990.
  
  Folien zu den Vortrag (ohne Bilder)
  
  
• Simulated Annealing
  (Klaus Schröder (ellern))
  
  • Literatur:
    • M. Jerrum and G. Sorokin, Simulated annealing for graph bisection in Proceedings of the 34th IEEE Symposium on Foundations of Computer Science (FOCS), 1993, and also Technical Report ECS-LFCS-93-260, Department of Computer Science, University of Edinburgh, April 1993.
  
  Folien zu den Vortrag (unkorrigiert)
  
  
• Estimating the Number of k-colorings of a Graph
  (Artur Czumaj (artur))
  
  • Literatur:
    • M. Jerrum, A Very Simple Algorithm for Estimating the Number of k-colourings of a Low-degree Graph, Random Structures and Algorithms, 7(2):157-165, 1995, and also Technical Report ECS-LFCS-94-290, Department of Computer Science, University of Edinburgh, April 1994.
  
  Folien zu den Vortrag (ohne Bilder, unkorriegiert)
  
  
• Deviation Bounds - Canceled
  
  • Literatur:
    • D. Gillman, A Chernoff bound for random walks on expander graphs, in Proceedings of the 34th IEEE Symposium on Foundations of Computer Science (FOCS), 1993.
    • N. Kahale, Large deviation bounds for Markov chains, Technical Report DIMACS TR-94-39, DIMACS, June 1994.