Algorithmic Graph Theory

During the course the typical graph problems will be discussed:

  • solve round trip problems,
  • calculate maximal flows,
  • find matchings and colourings,
  • analyze planar graphs.

Using the examples of graph problems, the students also will become familiar with more abstract concepts, for example, how to model problems as linear programs.

After the course students will be able to:

  • model typical problems in computer science as graph problems;
  • decide which tool from the course helps solve a given graph problem algorithmically;
  • practice how to formulate (graph) problems as linear problems;
  • learn how to estimate the running time of given graph algorithms.

Prerequisites

Algorithms and Data Structures (the concept of asymptotic running times, elementary data structures – arrays, lists, stacks, queues, and binary search trees).