Titolo

Docente(i)

Lingua

Breve descrizione

CFU / Ore

Periodo di erogazione

Title

Graph Theory and Algorithms

Teacher(s)

Prof. Gianluca della Vedova

Prof. Marco Viviani

Language

English

Short description

The course is an introduction to Graph Theory, without a specific application in mind.

Lecture plan:

  1. Introduction to Graph Theory: What is a graph? Basic concepts. Connectivity (connected components, reachability, biconnected components, spanning trees, bipartite graphs)
  2. Walks, Paths, Trials, Cycles (Hamiltonian cycles, Eulerian cycles, TSP)
  3. Graph Matching (perfect matching, algorithm on bipartite graphs)
  4. Graph Decomposition (Modular decomposition, cographs)
  5. Graph Coloring (perfect graphs). Treewidth, pathwidth, Twin-width
  6. Graph Compression
  7. Graph Embedding and Hyperbolicity
  8. Graph Mining (Intro & Graph Indexing)
  9. Graph Mining (Graph Summarization & Graph Classification)
  10. Graph Partitioning (and Clustering) & Complex Networks (graphs to represent complex systems and networks, small-world)

CFU / Hours

2.5 credits/20 hours

Teaching period

May 2021

Enrolment methods

  • Manual enrolments
  • Guest access
  • Self enrolment (Student)

Staff

    Manager

  • Picture of Gianluca Della Vedova
    Gianluca Della Vedova
  • Teacher

  • Picture of Marco Viviani
    Marco Viviani
  • Assistant

  • Picture of Mauricio Abel Soto Gomez
    Mauricio Abel Soto Gomez