DiarioDelleLezioni < Algoreti

Tags: view all tags

Home

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 CLASS

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: the 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/3)

(mobile) sensor networks
The problem of centralized deployment
The problem on graphs: min weight matching in bipartite graphs
maximum matching in bipartite graphs (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/3)

maximum matching in bipartite graphs (2)
- algorithm based on Berge's theorem
- Hopcroft & Karp algorithm
min weight perfect matching in bipartite graphs
- weighted augmenting paths
- an algorithm based on searching for augmenting paths
- ILP formulation
maximum matching in general graphs
- blossoms
- lemma on the cycle contraction
- Edmonds algorithm (idea)

Monday, November 17, 2025 (Lessons 37-38-39):

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

Another application

The Distributed Deployment of Sensors, i.e., the construction of a Voronoi Diagram (1/2)

The problem
A Possible Approach: Virtual Forces
A Protocol Based on Voronoi Diagrams
Voronoi Diagrams
- hypothesis of general position
- properties
- complexity
- the dual problem: Delaunay triangulation
Algorithms to compute the Voronoi diagram
- half-plane intersection (divide et impera)

Wednesday, November 19, 2025 (Lessons 40-41):

The Distributed Deployment of Sensors, i.e,. the construction of a Voronoi Diagram (2/2)

Algorithms to compute the Voronoi diagram
- Fortune algorithm
Heterogeneous sensors
- A new notion of distance: Laguerre distance
- Voronoi-Laguerre diagrams
- A protocol based on Voronoi-Laguerre distance

Monday, November 24, 2025 (Lessons 42-43-44):

Monitoring by UAVs, i.e., what? (+some open problems)