Return to Teaching

2017 – Graph Algorithms

Description

In mathematics and computer science, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. One can “observe graphs” everywhere. Virtually, any field of science, industry, commerce, politics, social life, etc. contains numerous cases of relations and processes that could be naturally represented in terms of graphs. One would need to apply computational methods from graph theory to address the related problems from real life. During this course we study a number of graph algorithms and discuss their implementation.

The goal of this course is to demonstrate how graph theory can be used to solve real-life problems. We consider here a number of major problems on graphs such as graph exploration, optimal paths search, tours on graphs, optimal network flow, etc., and demonstrate a number of exact and approximation algorithms solving them. We analyze the algorithms complexities and discuss their implementations.

Particularly, we focus on the following topics:

  • basic computational problems from graph theory and their relation to real life cases;
  • algorithms solving graph theoretic problems and analyze their complexity;
  • implementation of the algorithms on graphs.

Content

  •  search on graphs – depth-first search and breadth-first search algorithms;
  •  optimal path search – cheapest/shortest/longest path search algorithms;
  •  connectivity in graphs – edge and vertex connectivity, connected components;
  •  minimum spanning trees;
  •  Cliques, independent sets, coloring;
  •  Graph tours – Euler, Hamiltonian paths. Traveling salesman problem;
  •  Graph matching;
  •  Network flow – Max flow problem. Min-cost flow problem;

Prerequisites

  • Preferably: discrete mathematics concepts and graph theory (brief introduction of necessary concepts and notions will be given whenever necessary)
  • Some knowledge and skills in programming is appreciated, especially in Java language.

Course format

  • Lectures: 28h, 14 lectures
  • Exercises: 7 homework+demonstration sessions
  • Final examination:
    • 15 points – pass, mark 1/5
    • over 27 points -, mark 5/5
    • Bonus points from exercises
      • with enough gained bonus points one can skip the final exam, and even obtain the highest mark

Literature:

Credits:

  • 5sp

Time schedule:

  • Start date: 06th of September, 2017
  • End date: 19th of October, 2017
  • Wednesdays:
    • 13-15, 115A, Agora, Vattenborgsvägen 5, 20500 ÅBO
  • Thursdays:
    • 15-17, 115A, Agora, Vattenborgsvägen 5, 20500 ÅBO
  • Course exams:
    • 03.11.2017
    • 24.11.2017
  • Check the list below for more details (SUBJECT OF CHANGE):
  • September 6, 2017: Lecture 1: Introduction1:30 pm – 3:00 pm, 115A, Agora,slides
  • September 7, 2017: Lecture 2: Graph search algorithms3:15 pm – 5:00 pm, 115A, Agora,slides
  • September 13, 2017: Lecture 3: Graph search algorithms (cont.)1:30 pm – 3:00 pm, 115A, Agora,slides
  • September 14, 2017: Lecture 4: Path searching algorithms3:15 pm – 5:00 pm, 115A, Agora,slides
  • September 20, 2017: Lecture 5: Path searching algorithms (cont.)1:30 pm – 3:00 pm, 115A, Agora,slides
  • September 21, 2017: Lecture 6: Minimum spanning trees, optimum branchings3:15 pm – 5:00 pm, 115A, Agora,slides
  • September 27, 2017: Lecture 7: Circuits, cut-sets and connectivity1:30 pm – 3:00 pm, 115A, Agora,slides
  • September 28, 2017: Lecture 8: Connectivity, cliques and independent sets3:15 pm – 5:00 pm, 115A, Agora,slides
  • October 4, 2017: Lecture 9: Cliques, independent sets, colouring1:30 pm – 3:00 pm, 115A, Agora,slides
  • October 5, 2017: Lecture 10: Tours: Euler, Hamiltonian paths. Travelling salesman problem3:15 pm – 5:00 pm, 115A, Agora,slides
  • October 11, 2017: Lecture 11: Tours: Euler, Hamiltonian paths. Travelling salesman problem1:30 pm – 3:00 pm, 115A, Agora,slides
  • October 12, 2017: Lecture 12: Graph matching3:15 pm – 5:00 pm, 115A, Agora,slides
  • October 18, 2017: Lecture 13: Network flow, Max flow problem1:30 pm – 3:00 pm, 115A, Agora,slides
  • October 19, 2017: Lecture 14: Network flow, Max flow problem. Min-cost flow problem3:15 pm – 5:00 pm, 115A, Agora,slides

Lecturer:

  • Vladimir Rogojin,
  • Department of CS,
  • Åbo Akademi University,
  • vrogojin at abo.fi, room 342A, Agora, Vattenborgsvägen 5, 20500 ÅBO

Course assistant:

  • TBD

Registration (also for the exam)

Through MinPlan.