Weekly Notes for Week 21

• This week’s topics:

  • Continuation of ring perception.
  • Minimum cycle bases.
  • Horton’s algorithm and de Pina’s algorithm.
  • Comparing candidate-cycle based and witness-set based constructions.

• Interactive material:

  • MCB visualizer for small weighted graphs, including de Pina and Horton modes.
  • Parity lift visualizer for the shortest odd-intersection cycle subroutine used in the de Pina construction.

• Reading Material:

  • Mandatory (ring perception): Franziska Berger et al., Counterexamples in Chemical Ring Perception
  • Mandatory: Hanser T, Jauffret P, Kaufmann G (1996), A New Algorithm for Exhaustive Ring Perception in a Molecular Graph. J Chem Inf Comput Sci 36(6):1146-1152.
  • Voluntary: de Pina runtime / minimum cycle bases article

• Slides and notes:

  • Ring-perception notes
  • Horton / de Pina / minimum cycle bases
  • Additional cycle-basis slides
  • MOD framework addon

• Exercises:

  • Mandatory Exercise Sheet 01
  • Continue with Exercise Sheet 04 (preliminary).
  • Use the MCB visualizer to compare the de Pina and Horton constructions on the slide example and on small custom graphs.
  • In de Pina mode, each step links to the corresponding parity lift visualizer instance for the current set (S_k).