Course Material for the EPFL Zinal spring school, March 2002

The slides for all lectures are now available.

• Some of the Theory Behind LEDA (slides)

  In my first lecture I will give a survey of some of the theory underlying the LEDA system under five headings.
  • Algorithms
  • System Architecture
  • Correctness of Geometrical and Network Algorithms
  • Correctness of Implementations
  • Efficiency

  In later lectures I will discuss some of the topics in more detail.

• Certifying Graph Recognition Algorithms (slides)

  A recognition algorithm for a class of graphs is certifying if it gives proofs of membership and non-membership. Proofs of membership are typically a particular representation of the graph and proofs of non-membership are typically forbidden subgraphs of some sort. We discuss certifying recognition algorithms for planar graphs (pages 23 -- 68) and interval graphs.

• Graph Algorithms and Data Structures (slides1, slides2)

  The worst case running time of some graph algorithms can be improved considerably by the use of data structures: Priority queues for shortest path calculations, dynamic trees for maximum f flow, mergeable priorty queues for general weighted matching. Is it worth the effort? We discuss the issue for shortest paths and general weighted matchings.

• TSP-based Curve Reconstruction (slides)

  We discuss a polynomially solvable case of the Traveling Salesman Problem