Lesson Diary A.y. 2025-2026

Monday, September 22, 2025 (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

Wednesday, September 24, 2025 (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
  • the packet-switching model
  • the Butterfly network
  • routing on the Butterfly network: the greedy algorithm
  • The concept of blocking network, non-blocking network, and rearrangeable network

Monday, September 29 and Wednesday, October 1, 2025: NO Lessons

Monday, October 6, 2025 (Lessons 6-7-8):

The Routing Problem i.e., the Least Cost Path Problem (3/3)

• The Routing Problem on Interconnection Topologies
  • 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 the complete binary tree (H-tree)
• Collinear Layout of the Complete Network
• Layout of the Complete network
• Relation between bisection width and layout area
• Layout of the Butterfly network
  • The Wise layout

Wednesday, October 8, 2025 (Lessons 9-10):

The Problem of Laying out Interconnection Topologies, i.e., the Grid Orthogonal Drawing Problem (2/2)

• Layout of the Butterfly network
  • 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

Monday, October 13, 2025 (Lessons 11-12-13):

The problem of worm propagation/prevention, i.e., the Minimum Vertex Covering Problem (1)

• 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)
• A related problem: eternal vertex problem

Wednesday, October 15, 2025 (Lessons 14-15):

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
• Introduction to the frequency assignment problems
• Direct and hidden collisions, interference graph
• L(h,k)-labeling and minimum span (1)
  • Properties of the L(h,k)-labeling and their proofs

Monday, October 20, 2025 (Lessons 16-17-18):

A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2/2)

• L(h,k)-labeling and minimum span (2)
  • Proof of NP-completeness for diameter 2 graphs
  • 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
  • Exact results: stars
  • Exact results: trees
  • Exact results: paths
  • Exact results: cycles
  • Exact results: 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

Wednesday, October 22, 2025 (Lessons 19-20):

The minimum energy broadcast, i.e., the minimum spanning tree (1/2)

• The Min Broadcast problem
• NP-completeness and inapproximability results (reduction from Min Set Cover)
• Relation between Min Broadcast and Min Spanning Tree (MST)
• The MST problem
  • Kruskal algorithm

Monday, October 27, 2025 (Lessons 21-22-23):

The minimum energy broadcast, i.e., the minimum spanning tree (2/2)

• The MST problem
  • Prim algorithm
  • Boruvka algorithm
• The Min Broadcast problem
  • MST heuristics
  • SPT heuristics
  • BAIP heuristics
  • approximation ratio for MST

The data mule problem, i.e., the TSP (1/2)

• (Fixed) sensor networks
• The Data Mule problem
• The TSP
  • NP-completeness

Wednesday, October 29, 2025 (Lessons 24-25-26-27-28):

The data mule problem, i.e., the TSP (2/2)

• The TSP
  • inapproximability
  • special cases: metric TSP and Euclidean TSP
  • generalizations

The Data Collection in ad-hoc networks, i.e., the connected Dominating Set Problem

• the connected dominating set problem
• the dominating set problem
• the connected dominating set problems in unit disk graphs

Monday, November 3, 2025: NO CLASS

Wednesday, November 5, 2025 (Lessons 29-30-31): First Mid-term exam

Monday, November 10, 2026 (Lessons 32-33-34):

The centralized deployment of Mobile sensors, i.e., the perfect matching in Bipartite graphs (1)

• (mobile) sensor networks
• The problem of centralized deployment
• The problem on graphs: min weight matching in bipartite graphs
• maximum matching in a bipartite graph (1)
  • P. Hall's theorem (with proof)
  • searching for an augmenting path
  • Berge's theorem on the augmenting paths (with proof)

Wednesday, November 12, 2026 (Lessons 35-36):

The centralized deployment of Mobile sensors, i.e., the perfect matching in Bipartite graphs (2)

• maximum matching in a bipartite graph (2)
  • algorithm based on Berge's theorem
  • Hopcroft & Karp algorithm
  • augmenting paths
  • an algorithm based on searching for augmenting paths
  • ILP formulation

Lesson Diary of the Previous Years