↑ Return to Teaching

Graph Algorithms 2017

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
  • September 6, 2017: Lecture 1: Introduction
    1:30 pm - 3:00 pm, 115A, Agora,
September 7, 2017
  • September 7, 2017: Lecture 2: Graph search algorithms
    3:15 pm - 5:00 pm, 115A, Agora,
September 13, 2017
  • September 13, 2017: Lecture 3: Graph search algorithms (cont.)
    1:30 pm - 3:00 pm, 115A, Agora,
September 14, 2017
  • September 14, 2017: Lecture 4: Path searching algorithms
    3:15 pm - 5:00 pm, 115A, Agora,
September 20, 2017
  • September 20, 2017: Lecture 5: Path searching algorithms (cont.)
    1:30 pm - 3:00 pm, 115A, Agora,
September 21, 2017
  • September 21, 2017: Lecture 6: Minimum spanning trees, optimum branchings
    3:15 pm - 5:00 pm, 115A, Agora,
September 27, 2017
  • September 27, 2017: Lecture 7: Circuits, cut-sets and connectivity
    1:30 pm - 3:00 pm, 115A, Agora,
September 28, 2017
  • September 28, 2017: Lecture 8: Connectivity, cliques and independent sets
    3:15 pm - 5:00 pm, 115A, Agora,
October 4, 2017
  • October 4, 2017: Lecture 9: Cliques, independent sets, colouring
    1:30 pm - 3:00 pm, 115A, Agora,
October 5, 2017
  • October 5, 2017: Lecture 10: Tours: Euler, Hamiltonian paths. Travelling salesman problem
    3:15 pm - 5:00 pm, 115A, Agora,
October 11, 2017
  • October 11, 2017: Lecture 11: Tours: Euler, Hamiltonian paths. Travelling salesman problem
    1:30 pm - 3:00 pm, 115A, Agora,
October 12, 2017
  • October 12, 2017: Lecture 12: Graph matching
    3:15 pm - 5:00 pm, 115A, Agora,
October 18, 2017
  • October 18, 2017: Lecture 13: Network flow, Max flow problem
    1:30 pm - 3:00 pm, 115A, Agora,
October 19, 2017
  • October 19, 2017: Lecture 14: Network flow, Max flow problem. Min-cost flow problem
    3:15 pm - 5:00 pm, 115A, Agora,

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.

Projects

TBD

View page »

Graph Algorithms 2016

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 …

View page »

Graph Algorithms 2014

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 …

View page »