LESSON DIARY
Monday, 28 September 2026 (lessons 1-2-3)
First day: welcome!
Introduction
The Routing Problem, i.e., the Least Cost Path Problem (1/3)
The routing Problem
The Shortest Path Problem
Shortest paths: BFS
A parenthesis on the Connected Components Problem and its applications
The least cost path Problem (1/2)
The negative cycle issue and its applications
Least cost paths: introduction
Bellman-Ford algorithm
Dijkstra algorithm
Thursday, 1 October 2026 (lessons 4-5)
The Routing Problem, i.e., the Least Cost Path Problem (2/3)
The least cost path Problem (2/2)
Floyd-Warshall algorithm
The Routing Problem on Interconnection Topologies (1/2)
The packet-switching model
The Butterfly network
Routing on the Butterfly network: the greedy algorithm
The concept of blocking network, non-blocking network
Monday, 5 October 2026 (lessons 6-7-8)
The Routing Problem, i.e., the Least Cost Path Problem (3/3)
The Routing Problem on Interconnection Topologies (2/2)
The Benes network
Routing on the Benes network: the looping algorithm
The Problem of Laying out Interconnection Topologies, i.e., the Grid Orthogonal Drawing Problem (1/2)
The Thompson model
The orthogonal grid drawing of graphs
Layout of Interconnection topologies
Layout of the complete binary tree (H-tree)
Collinear Layout of the Complete Network
Thursday, 8 October 2026 - no lesson
Monday, 12 October 2026 (lessons 9-10-11)
The Problem of Laying out Interconnection Topologies, i.e., the Grid Orthogonal Drawing Problem (2/2)
Relation between bisection width and layout area
Layout of the Complete Network
Layout of the Butterfly network
The Wise layout
The Even & Even layout
Comparison between the two methods
Optimal area layout
Layout of the Hypercube network
Collinear layout
General layout
The 3D layout problem
Thursday, 15 October 2026 (lessons 12-13)
The problem of worm propagation/prevention, i.e., the Minimum Vertex Covering Problem (1/2)
The problem
worms
damages caused by worms
Model of the problem on graphs: minimum vertex cover
Definition
ILP model
a 2-approximation algorithm
independent set and maximum matching in relation to vertex cover
Another approximation algorithm
Model of the problem on graphs: minimum vertex cover
Konig-Egevary theorem (without proof)
Monday, 19 October 2026 (lessons 14-15-16)
The problem of worm propagation/prevention, i.e., the Minimum Vertex Covering Problem (2/2)
A related problem: the eternal vertex problem
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1/2)
Introduction to the frequency assignment problems
Direct and hidden collisions, interference graph
L(h,k)-labeling and minimum span
Properties of the L(h,k)-labeling and their proofs
Proof of NP-completeness for diameter 2 graphs
Thursday, 22 October 2026 (lessons 17-18)
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2/2)
L(h,k)-labeling and minimum span
Lower bound of Delta+1 on lambda
Example: a graph requiring lambda=Delta squared - Delta
Upper bound of Delta squared + 2 Delta
Griggs and Yeh's conjecture
Exact results: cliques, stars, trees, paths, cycles, grids
Approximate results: outerplanar graphs
Variations of the problem
oriented L(2,1)-labeling
L(h1, ..., hk)-labeling
backbone coloring
multiple L(h,k)-labeling
a parenthesis on the 4-color theorem
The minimum Energy Broadcast i.e. the min Spanning Tree (1/2)
The problem
Monday, 26 October 2026 (lessons 19-20-21)
The minimum Energy Broadcast i.e. the min Spanning Tree (2/2)
Inapproximability of MinBroadcast in the general setting
Euclidean MinBroadcast
The min Spanning Tree Problem (recup)
properties of a min Spanning Tree
Kruskal algorithm
Prim algorithm
Boruvka Algorithm
Other algorithms
Again on minBrodcast
SPT heuristics
BAIP heuristics
MST heuristics
Week devoted to exam:
Tuesday, 3 November 2026 First mid term exam (lessons 22-23-24)
Thursday, 5 November 2026 (lessons 25-26)
Monday, 9 November 2026 (lessons 27-28-29)
Thursday, 12 November 2026 (lessons 30-31)
Monday, 16 November 2026 (lessons 32-33-34)
Thursday, 19 November 2026 (lessons 35-36)
Monday, 23 November 2026 (lessons 37-38-39)
Thursday, 26 November 2026 (lessons 40-41)
Opis questionnaire
Monday, 30 November 2026 (lessons 42-43-44)
Thursday, 3 December 2026 (lessons 45-46)
Monday, 7 December 2026 NO LESSON
Thursday, 10 December 2026 (lessons 47-48)
Monday, 14 December 2026 (lessons 49-50-51)
Thursday, 17 December 2026 (lessons 52-53)
Monday, 21 December 2026: second mid term exam (lessons 54-55-56)