Lesson Diary of the Previous Years
Lesson Diary A.y. 2022-2023
Tuesday September 27, 2022 (Lessons 1-2-3):
Introduction
The Routing Problem i.e. the Least Cost Path Problem (1)
- The routing Problem
- The shortest path Problem
- The least cost path Problem (1)
- the negative cycle issue
- least cost paths: introduction
- Bellman-Ford algorithm
- Dijkstra algorithm
Friday September 30, 2022 (Lessons 4-5):
The Routing Problem i.e. the Least Cost Path Problem (2)
- The least cost path Problem (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
- the Benes network
- routing on the Benes network: the looping algorithm
Tuesday October 4, 2022 (Lessons 6-7-8):
The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (1)
- 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
- the Even & Even layout
- comparison between the two methods
Friday October 7, 2022 (Lessons 9-10):
The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (3)
- Layout of the Butterfly network
- Layout of the Hypercube network
- Collinear layout
- general layout
- The 3D layout problem
Tuesday October 11, 2022 (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 with vertex cover
- another approximation algorithm
- Konig-Egevary theorem (without proof)
- A related problem: eternal vertex problem
Friday October 14, 2022 (Lessons 14-15):
The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem
- The problem of minimizing boolean functions
- Model of the problem on graphs: the Minimum Set Cover Problem
- definition
- ILP formulation
- relation with the Minimum Vertex Covering Problem
- an O(log n)-approximation algorithm
- another approximation algorithm
- some related problems:
- Hitting set problem
- Edge Cover problem
- Set Packing problem
- Exact Cover problem
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1)
- Introduction to the frequency assignment problems
Tuesday October 18, 2022 (Lessons 16-17-18):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)
- 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)
- The special case h=k in relation to the suqre of a graph
- Properties of the L(h,k)-labeling and their proofs
- Proof of NP-completeness for diameter 2 graphs
Friday October 21, 2022 (Lessons 19-20):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)
- L(h,k)-labeling and minimum span (2)
- 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
Tuesday October 25, 2022 (Lessons 21-22-23):
students' lesson 1: The Routing problem i.e. the minimum cost shortest path
students' lesson 2: The layout of interconnection networks i.e. the orthogonal grid graph drawing
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)
- Variations of the problem
- oriented L(2,1)-labeling
- L(h1, ..., hk)-labeling
- backbone coloring
- multiple L(h,k)-labeling
- frequency assignment in GSM networks
- a parenthesis on the 4 color theorem
Friday October 28, 2022 (Lessons 24-25):
The minimum energy broadcast i.e. the minimum spanning tree (1)
- 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
- Prim algorithm
- Boruvka algorithm
Tuesday November 1, 2022: HOLIDAY
Friday November 4, 2022 (Lessons 26-27):
students' lesson 3: The problem of infecting a network with a worm i.e. the minimum vertex cover problem
The minimum energy broadcast i.e. the minimum spanning tree (2)
- the Min Broadcast problem
- MST heuristics
- SPT heuristics
- BAIP heuristics
- approximation ratio for MST
The data mule problem i.e. the TSP (1)
- (Fixed) sensor networks
- The Data Mule problem
Tuesday November 8, 2022 (Lessons 28-29-30):
students' lesson 4: The problem of minimizing a boolean circuit i.e. the minimum set covering problem
The data mule problem i.e. the TSP (2)
- The TSP
- NP-completeness
- inapproximability
- special cases: metric TSP and Euclidean TSP
- generalizations
the Data Collection in ad-hoc networks i.e. the connected Dominating Set Problem (1)
- the data collection problem
Friday November 11, 2022 (Lessons 31-32-33): FIRS MID-TERM EXAM
Tuesday November 15, 2022 (Lessons 34-35-36):
students' lesson 5: The frequency assignment problem i.e. a graph coloring problem
students' lesson 6: The minimum energy broadcast problem i.e. the minimum spanning tree problem
the Data Collection in ad-hoc networks i.e. the connected Dominating Set Problem (2)
- the connected dominating set problem
- the dominating set problem
- the connected dominating set problems in unit disk graphs
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (1)
Friday November 18, 2022 (Lessons 37-38):
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (2)
- the problem of centralized deployment
- the problem on graphs: min weight matching in a bipartite graphs
- maximum matching in a bipartite graph
- P. Hall theorem (with proof)
- corollary to the P. Hall theorem
- searching an augmenting path
- Berge theorem on the augmenting paths
- algorithm based on Berge theorem
- Hopcroft & Karp algorithm
Tuesday November 22, 2022 (Lessons 39-40-41):
students' lesson 7: The data mule scheduling problem i.e. the travelling salesman problem
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (3)
- Minimum weight perfect matching in bipartite graphs (cntd)
- augmenting paths
- an algorithm based on searching augmenting paths
- ILP formulation
- Maximum matching in general graphs
- blossoms
- lemma on the cycle contraction
- Edmonds algorithm (idea)
- Another application
Friday November 25, 2022 (Lessons 42-43):
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (1)
- The problem
- A Possible Approach: Virtual Forces
- A Protocol Based on Voronoi Diagrams
- Voronoi Diagrams
- hypthesis of general position
- properties
- complexity
- the dual problem: Delaunay triangulation
Tuesday November 29, 2022 (Lessons 44-45-46):
students' lesson 8: The centralized deployment of a mobile sensor network i.e. the minimum cost perfect matching in bipartite graphs
students'opinions questionnaire - OPIS code: R053WYBC
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)
- Algorithms to compute the Voronoi diagram
- half-plane intersection (divide et impera)
- Fortune algorithm
Friday December 2, 2022 (Lessons 47-48):
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (3)
- Heterogeneous sensors
- A new notion of distance: Laguerre distance
- Voronoi-Laguerre diagrams
- A protocol based on Voronoi-Laguerre distance
Tuesday December 6, 2022 (Lessons 49-50-51):
students' lesson 9: Self-deployment of a mobile sensor network i.e. the Voronoi Diagram
Monitoring by UAVs i.e. the multiple TSP with constraints
Friday December 9, 2022: LONG WEEKEND: the University is closed
Tuesday December 13, 2022 (Lessons 52-53-54)
students' lesson 10: Monitoring by UAVs i.e. the multiple TSP with constraints
Other kinds of networks: the phylogeny and medicine cases (+some open problems)
Friday December 16, 2022 (Lessons 55-56): no lesson
*Tuesday December 20, 2022 (Lessons 57-58-59): SECOND
MID-TERM EXAM*
Lesson Diary A.y. 2021-2022
Wednesday September 22, 2021 (Lessons 1-2-3):
Introduction
The Routing Problem i.e. the Least Cost Path Problem (1)
- The routing Problem
- The shortest path Problem
- The least cost path Problem
- the negative cycle issue
- least cost paths: introduction
Friday September 24, 2021:
No lesson
Wednesday September 29, 2021 (Lessons 4-5-6):
The Routing Problem i.e. the Least Cost Path Problem (2)
- The least cost path Problem
- Bellman-Ford algorithm
- Dijkstra algorithm
- Floyd-Warshall algorithm
- The Routing Problem on Interconnection Topologies
- the packet switching model
- the Butterfly network
- routing on the Butterfly network: the greedy algorithm
Friday October 1, 2021 (Lessons 7-8):
The Routing Problem i.e. the Least Cost Path Problem (3)
- The Routing Problem on Interconnection Topologies
- the concept of blocking network, non-blocking network and rearrangeable network
- 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)
- The Thompson model
- The orthogonal grid drawing of graphs
Wednesday October 6, 2021 (Lessons 9-10-11):
The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)
- 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
- the Even & Even layout
Friday October 8, 2021 (Lessons 12-13):
The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (3)
- Layout of the Butterfly network
- summary of the last lesson hour (the video went lost)
- comparison between the two methods
- Layout of the Hypercube network
- Collinear layout
- general layout
- The 3D layout problem
Wednesday October 13, 2021 (Lessons 14-15-16):
A parenthesis: Some problems in (co-)phylogeny (some theses' proposals)
The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (2)
- The problem
- worms
- damages caused by worms
Friday October 15, 2021 (Lessons 17-18):
The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (2)
- Model of the problem on graphs: minimum vertex cover
- definition
- ILP model
- a 2-approximation algorithm
- independent set and maximum matching in relation with vertex cover
- another approximation algorithm
- Konig-Egevary theorem (without proof)
- A related problem: eternal vertex problem
Wednesday October 20, 2021 (Lessons 19-20-21):
The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem
- The problem of minimizing boolean functions
- Model of the problem on graphs: the Minimum Set Cover Problem
- definition
- ILP formulation
- relation with the Minimum Vertex Covering Problem
- an O(log n)-approximation algorithm
- another approximation algorithm
- some related problems:
- Hitting set problem
- Edge Cover problem
- Set Packing problem
- Exact Cover problem
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1)
- Introduction to the frequency assignment problems
- Direct and hidden collisions, interference graph
Friday October 22, 2021 (Lessons 22-23):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1)
- Introduction to the frequency assignment problems
- Direct and hidden collisions, interference graph
- L(h,k)-labeling and minimum span (1)
- The special case h=k in relation to the suqre of a graph
- Properties of the L(h,k)-labeling and their proofs
- Proof of NP-completeness for diameter 2 graphs (first part)
Wednesday October 27, 2021 (Lessons 24-25-26):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)
- L(h,k)-labeling and minimum span (2)
- Proof of NP-completeness for diameter 2 graphs
- Lower bound of Delta+1 on lambbda
- 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
Friday October 29, 2021 (Lessons 27-28-29):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)
- L(h,k)-labeling and minimum span (3)
- Approximate results: outerplanar graphs
- Variations of the problem (1)
- oriented L(2,1)-labeling
- L(h1, ..., hk)-labeling
- backbone coloring
- multiple L(h,k)-labeling
- frequency assignment in GSM networks
Week November 2-5, 2021: Mid-term exams
Wednesday November 10, 2021 (Lessons 30-31-32):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (4)
- L(h,k)-labeling and minimum span (4)
- Variations of the problem (2)
- a parenthesis on the 4 color theorem
The minimum energy broadcast i.e. the minimum spanning tree (1)
- the Min Broadcast problem
- NP-completeness and inapproximability results (reduction from Min Set Cover)
- Relation between Min Broadcast and Min Spanning Tree (MST)
Friday November 12, 2021 (Lessons 33-34):
The minimum energy broadcast i.e. the minimum spanning tree (2)
- The MST problem
- Kruskal algorithm
- Prim algorithm
- Boruvka algorithm
Wednesday November 17, 2021 (Lessons 35-36-37):
The minimum energy broadcast i.e. the minimum spanning tree (3)
- the Min Broadcast problem
- MST heuristics
- SPT heuristics
- BAIP heuristics
- approximation ratio for MST
The data mule problem i.e. the TSP (1)
- (Fixed) sensor networks
- The Data Mule problem
- The TSP
- NP-completeness
- inapproximability
Friday November 19, 2021 (Lessons 38-39):
The data mule problem i.e. the TSP (2)
-
- special cases: metric TSP and Euclidean TSP
- generalizations
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (1)
Wednesday November 24, 2021 (Lessons 40-41-42):
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (2)
- the problem of centralized deployment
- the problem on graphs: min weight matching in a bipartite graphs
- maximum matching in a bipartite graph
- P. Hall theorem (with proof)
- corollary to the P. Hall theorem
- searching an augmenting path
- Berge theorem on the augmenting paths
- algorithm based on Berge theorem
- Hopcroft & Karp algorithm
Friday November 26, 2021 (Lessons 43-44):
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (3)
- Minimum weight perfect matching in bipartite graphs (cntd)
- augmenting paths
- an algorithm based on searching augmenting paths
- ILP formulation
- Maximum matching in general graphs
- blossoms
- lemma on the cycle contraction
- Edmonds algorithm (idea)
- Another application
Wednesday December 1, 2021 (Lessons 45-46-47):
Students' lessons
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (1)
- The problem
- A Possible Approach: Virtual Forces
- A Protocol Based on Voronoi Diagrams
- Voronoi Diagrams
- hypthesis of general position
- properties
- complexity
- the dual problem: Delaunay triangulation
Friday December 3, 2021 (Lessons 48-49):
Students' lessons [BKTL04], [BPT00], [Bal07], [AGK08], [Xal14]
Wednesday December 8, 2021: HOLIDAY
Friday December 10, 2021 (Lessons 50-51):
Students' lessons [M95], [Cal15]
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)
- Algorithms to compute the Voronoi diagram
- half-plane intersection (divide et impera)
- Fortune algorithm
Wednesday December 15, 2021 (Lessons 52-53-54):
Students' lessons [HZ14], [YWD06], [NSM16], [ML18]
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (3)
- Heterogeneous sensors
- A new notion of distance: Laguerre distance
- Voronoi-Laguerre diagrams
- A protocol based on Voronoi-Laguerre distance
Monitoring by UAVs i.e. what? (some theses' proposals)
Friday December 17, 2021 (Lessons 55-56): mid-term exam
Wednesday December 22, 2021: no lesson
--
Lesson Diary A.y. 2020-2021
Wednesday October 7, 2020 (Lessons 1-2-3):
Introduction
The Routing Problem i.e. the Least Cost Path Problem (1)
- The routing Problem
- The shortest path Problem
- The least cost path Problem
- the negative cycle issue
- least cost paths: introduction
Friday October 9, 2020 (Lessons 4-5):
The Routing Problem i.e. the Least Cost Path Problem (2)
- The least cost path Problem
- Bellman-Ford algorithm
- Dijkstra algorithm
- Floyd-Warshall algorithm
- The Routing Problem on Interconnection Topologies
- the packet switching model
- the Butterfly network
- routing on the Butterfly network: the greedy algorithm
Wednesday October 14, 2020 (Lessons 6-7-8):
The Routing Problem i.e. the Shortest Path Problem (3)
- The Routing Problem on Interconnection Topologies (2)
- the concept of blocking network, non-blocking network and rearrangeable network
- 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)
- The Thompson model
- The orthogonal grid drawing of graphs
- Collinear Layout of the Complete network
- Layout of the Complete network
- Relation between bisection width and layout area
- Layout of the Butterfly network
Friday October 16, 2020 (Lessons 9-10):
The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)
- Layout of the Butterfly network
- the Even & Even layout
- comparison between the two methods
- Layout of the Hypercube network
- Collinear layout
- general layout
- The 3D layout problem
Wednesday October 21, 2020 (lessons 11-12-13):
The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem
- 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 with vertex cover
- another approximation algorithm
- Konig-Egevary theorem (without proof)
- A related problem: eternal vertex problem
Friday October 23, 2020 (lessons 14-15):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1)
- Introduction to the frequency assignment problems
- Direct and hidden collisions, interference graph
- L(h,k)-labeling and minimum span (1)
- The special case h=k in relation to the suqre of a graph
- Properties of the L(h,k)-labeling and their proofs
Wednesday October 28, 2020 (lessons 16-17-18):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)
- L(h,k)-labeling and minimum span (2)
- Proof of NP-completeness for diameter 2 graphs
- Lower bound of Delta+1 on lambbda
- 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
- Approximate results: outerplanar graphs
- Variations of the problem
- oriented L(2,1)-labeling
- L(h1, ..., hk)-labeling
- backbone coloring
- multiple L(h,k)-labeling
- frequency assignment in GSM networks
- a parenthesis on the 4 color theorem
Friday October 30, 2020 (lessons 19-20):
The minimum energy broadcast i.e. the minimum spanning tree (1)
- the Min Broadcast problem
- NP-completeness and inapproximability results (reduction from Min Set Cover)
- Relation between Min Broadcast and Min Spanning Tree (MST)
Wednesday November 4, 2020 (lessons 21-22-23):
The minimum energy broadcast i.e. the minimum spanning tree (2)
- The MST problem
- Kruskal algorithm
- Prim algorithm
- Boruvka algorithm
- the Min Broadcast problem
- MST heuristics
- SPT heuristics
- BAIP heuristics
- approximation ratio for SPT
Friday November 6, 2020 (lessons 24-25):
The data mule problem i.e. the TSP (1)
- (Fixed) sensor networks
- The Data Mule problem
- The TSP
- NP-completeness
- inapproximability
Wednesday November 11, 2020 (lessons 26-27-28):
The data mule problem i.e. the TSP (2)
-
- special cases: metric TSP and Euclidean TSP
- generalizations
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 a bipartite graphs
- maximum matching in a bipartite graph
- P. Hall theorem (with proof)
- corollary to the P. Hall theorem
- searching an augmenting path
Friday November 13, 2020 (lessons 29-30):
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (2)
- maximum matching in a bipartite graph (cntd)
- Berge theorem on the augmenting paths
- algorithm based on Berge theorem
- Hopcroft & Karp algorithm
- Minimum weight perfect matching in bipartite graphs
- augmenting paths
- an algorithm based on searching augmenting paths
- ILP formulation
- Maximum matching in general graphs
- blossoms
- lemma on the cycle contraction
Wednesday November 18, 2020 (lessons 31-32-33):
Students' lessons (1)
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (3)
- Maximum matching in general graphs (cntd)
- blossoms
- lemma on the cycle contraction
- Edmonds algorithm (idea)
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (1)
- The problem
- A Possible Approach: Virtual Forces
- A Protocol Based on Voronoi Diagrams
- Voronoi Diagrams
- hypthesis of general position
Friday November 20, 2020 (lessons 34-35):
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)
- Voronoi Diagrams (cntd)
- properties
- complexity
- the dual problem: Delaunay triangulation
- Algorithms to compute the Voronoi diagram (1)
- half-plane intersection (divide et impera)
Wednesday November 25, 2020 (lessons 36-37-38):
Students' lessons (2)
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (3)
- Voronoi Diagrams (cntd)
- Heterogeneous sensors
- A new notion of distance: Laguerre distance
- Voronoi-Laguerre diagrams
- A protocol based on Voronoi-Laguerre distance
Friday November 27, 2020 (lessons 39-40):
Mid Term Exam 1/2
Wednesday December 2, 2020 (lessons 41-42-43):
Students' lessons (3)
The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem
- The problem of minimizing boolean functions
- Model of the problem on graphs: the Minimum Set Cover Problem
- definition
- ILP formulation
- relation with the Minimum Vertex Covering Problem
- an O(log n)-approximation algorithm
- another approximation algorithm
- some related problems:
- Hitting set problem
- Edge Cover problem
- Set Packing problem
- Exact Cover problem
Friday December 4, 2020 (lessons 44-45):
Monitoring by UAVs i.e. what? (some theses' proposals)
Wednesday December 9, 2020 (lessons 46-47-48):
Students' lessons (4)
- Dr. Federico Corò: "A Realistic Model to Support Rescue Operationsby UAVs after an Earthquake"
Friday December 11, 2020 (lessons 49-50):
Some problems in (co-)phylogeny (some further theses' proposals)
Wednesday December 16, 2020 (lessons 51-52-53):
Students' lessons (5)
Friday December 18, 2020 (lessons 54-55):
Mid Term Exam 2/2
Lesson Diary A.y. 2019-2020
Wednesday September 25, 2019 (Lessons 1-2-3):
Introduction
The Routing Problem i.e. the Least Cost Path Problem (1)
- The routing Problem
- The shortest path Problem
- The least cost path Problem
- the negative cycle issue
- least cost paths: introduction
- Bellman-Ford algorithm
- Dijkstra algorithm
- Floyd-Warshall algorithm
Friday September 27, 2019 (Lessons 4-5):
The Routing Problem i.e. the Least Cost Path Problem (2)
- 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
- the Benes network
- routing on the Benes network: the looping algorithm
Wednesday October 2, 2019 (Lessons 6-7-8):
The Routing Problem i.e. the Shortest Path Problem (3)
- The Routing Problem on Interconnection Topologies (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)
- The Thompson model
- The orthogonal grid drawing of graphs
- Collinear Layout of the Complete network
- Layout of the Complete network
- Relation between bisection width and layout area
Friday October 4, 2019 (lessons 9-10):
The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)
- Layout of the Butterfly network
- the Wise layout
- the Even & Even layout
- comparison between the two methods
- Layout of the Hypercube network
- Collinear layout
- general layout
- The 3D layout problem
Wednesday October 9, 2019 (lessons 11-13):
The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem
- 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 with vertex cover
- another approximation algorithm
- Konig-Egevary theorem
Friday October 11, 2019 (lessons 14-15):
The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem
- The problem of minimizing boolean functions
- Model of the problem on graphs: the Minimum Set Cover Problem
- definition
- ILP formulation
- relation with the Minimum Vertex Covering Problem
- an O(log n)-approximation algorithm
- another approximation algorithm
- some related problems:
- Hitting set problem
- Edge Cover problem
- Set Packing problem
- Exact Cover problem
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1)
- Introduction to the frequency assignment problems
Wednesday October 16, 2019 (lessons 16-18):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)
- Direct and hidden collisions, interference graph
- L(h,k)-labeling and minimum span (1)
- The special case h=k in relation to the suqre of a graph
- Properties of the L(h,k)-labeling and their proofs
- Proof of NP-completeness for diameter 2 graphs
Friday October 18, 2019 (lessons 19-20):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)
- L(h,k)-labeling and minimum span (2)
- Lower bound of Delta+1 on lambbda
- 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
- Approximate results: outerplanar graphs
Wednesday October 23, 2019 (lessons 21-23):
Lesson cancelled (due to illness of the teacher)
Friday October 25, 2019 (lessons 24-25):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (4)
- Variations of the problem
- oriented L(2,1)-labeling
- L(h1, ..., hk)-labeling
- backbone coloring
- multiple L(h,k)-labeling
- frequency assignment in GSM networks
- a parenthesis on the 4 color theorem
The minimum energy broadcast i.e. the minimum spanning tree (1)
- the Min Broadcast problem
- NP-completeness and inapproximability results (reduction from Min Set Cover)
- Relation between Min Broadcast and Min Spanning Tree (MST)
Wednesday October 29, 2019 (lessons 26-28):
The minimum energy broadcast i.e. the minimum spanning tree (2)
- The MST problem
- Kruskal algorithm
- Prim algorithm
- Boruvka algorithm
- the Min Broadcast broblem
- MST euristic
- SPT euristic
- BAIP euristic
- approximation ratio for SPT
Friday November 1, 2019 (lessons 26-27):
Holiday
Wednesday November 6, 2019 (lessons 28-30):
Midterm Exam
Friday November 8, 2019 (lessons 31-32):
The data mule problem i.e. the TSP
- (Fixed) sensor networks
- The Data Mule problem
- The TSP
- NP-completeness
- inapproximability
- special cases: metric TSP and Euclidean TSP
- generalizations
Wednesday November 13, 2019 (lessons 33-35):
Student Lessons with the presence of the teacher (1)
see
http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti
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 a bipartite graphs
Friday November 15, 2019 (lessons 36-37):
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (2)
- maximum matching in a bipartite graph
- P. Hall theorem (with proof)
- corollary to the P. Hall theorem
- searching an augmenting path
- Berge theorem on the augmenting paths
- algorithm based on Berge theorem
- Hopcroft & Karp algorithm
- Minimum weight perfect matching in bipartite graphs
- augmenting paths
- an algorithm based on searching augmenting paths
- ILP formulation
Wednesday November 20, 2019 (lessons 38-40):
Student Lessons with the presence of the teacher (2)
see
http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (3)
- Maximum matching in general graphs
- blossoms
- lemma on the cycle contraction
- Edmonds algorithm (idea)
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (1)
- The problem
- A Possible Approach: Virtual Forces
- A Protocol Based on Voronoi Diagrams
Friday November 22, 2019 (lessons 41-42):
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)
- Voronoi Diagrams
- hypthesis of general position
- properties
- complexity
- the dual problem: Delaunay triangulation
- Algorithms to compute the Voronoi diagram (1)
- half-plane intersection (divide et impera)
Wednesday November 27, 2019 (lessons 43-45):
Student Lessons with the presence of the teacher (3)
see
http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti
EVALUATION OF THE COURSE
Friday November 29, 2019 (lessons 46-47):
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (3)
- Algorithms to compute the Voronoi diagram (2)
- Heterogeneous sensors
- A new notion of distance: Laguerre distance
- Voronoi-Laguerre diagrams
- A protocol based on Voronoi-Laguerre distance
Wednesday December 4, 2019 (lessons 48-50):
Student Lessons with the presence of the teacher (4)
see
http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti
Monitoring by UAVs i.e. what? (some theses' proposals)
Friday December 6, 2019 (lessons 51-52):
Some problems in (co-)phylogeny (some further theses' proposals)
Wednesday December 11, 2019 (lessons 51-53):
Student Lessons with the presence of the teacher (5)
see
http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti
Winner Announcement: Award for the best students' lesson
Friday December 13, 2019 (lessons 53-54):
Phylogenetic Networks by Prof. B. Sinaimeri (INRIA Grenoble)
Wednesday December 18, 2019 (lessons 55-57):
Midterm Exam
Lesson Diary A.y. 2018-2019
Tuesday September 25, 2018 (Lessons 1-2,5):
Introduction
The Routing Problem i.e. the Shortest Path Problem (1)
- The routing Problem
- The shortest path Problem (1)
- shortest paths: BFS
- the negative cycle issue
- least cost paths: introduction
Thursday September 27, 2018 (Lessons 2,5-5):
The Routing Problem i.e. the Shortest Path Problem (2)
- The shortest path Problem (2)
- least cost paths (cnt.d): * Bellman-Ford algorithm
- Dijkstra algorithm
- Floyd-Warshall algorithm
- The Routing Problem on Interconnection Topologies (1)
- 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
Tuesday October 2, 2018 (Lessons 5-7,5):
The Routing Problem i.e. the Shortest Path Problem (3)
- The Routing Problem on Interconnection Topologies (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)
- The Thompson model
- The orthogonal grid drawing of graphs
- Collinear Layout of the Complete network
- Layout of the Complete network
Thursday October 4, 2018 (lessons 7,5-10):
The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)
- Relation between bisection width and layout area
- Layout of the Butterfly network (1)
- the Wise layout
- the Even & Even layout
- comparison between the two methods
Tuesday October 9, 2018 (lessons 10-12,5):
The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (3)
- Layout of the Hypercube network
- Collinear layout
- general layout
- The 3D layout problem
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 (1)
Thursday October 11, 2018 (lessons 12,5-15):
The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (2)
- Model of the problem on graphs: minimum vertex cover (2)
- a 2-approximation algorithm
- independent set and maximum matching in relation with vertex cover
- another approximation algorithm
- Konig-Egevary theorem
Tuesday October 16, 2018 (lessons 15-17,5):
The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem
- The problem of minimizing boolean functions
- Model of the problem on graphs: the Minimum Set Cover Problem
- definition
- ILP formulation
- relation with the Minimum Vertex Covering Problem
- an O(log n)-approximation algorithm
- another approximation algorithm
- some related problems:
- Hitting set problem
- Edge Cover problem
- Set Packing problem
- Exact Cover problem
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1)
- Introduction to the frequency assignment problems
Thursday October 18, 2018 (lessons 17,5-20):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)
- Direct and hidden collisions, interference graph
- L(h,k)-labeling and minimum span (1)
- The special case h=k in relation to the square of a graph
- Properties of the L(h,k)-labeling and their proofs
- Proof of NP-completeness for diameter 2 graphs
Tuesday October 23, 2018 (lessons 20-22,5):
Student Lessons with the presence of the teacher (1)
see
http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti
Thursday October 25, 2018 (lessons 22,5-25):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)
- L(h,k)-labeling and minimum span (2)
- Lower bound of Delta+1 on lambbda
- 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
Tuesday October 30, 2018:
Lesson canceled by the Dean.
Thursday November 1, 2018:
Holiday.
Tuesday November 6, 2018 (lessons 25-27,5):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (4)
- L(h,k)-labeling and minimum span (3)
- Approximate results: outerplanar graphs
- variations of the problem
- oriented L(2,1)-labeling
- L(h1, ..., hk)-labeling
- backbone coloring
- multiple L(h,k)-labeling
- frequency assignment in GSM networks
- a parenthesis on the 4 color theorem
The minimum energy broadcast i.e. the minimum spanning tree (1)
- the Min Broadcast problem
- NP-completeness and inapproximability results (reduction from Min Set Cover)
- Relation between Min Broadcast and Min Spanning Tree (MST)
Thursday November 8, 2018 (lessons 27,5-30):
Mid term exam
Tuesday November 13, 2018 (lessons 30-32,5):
Student Lessons with the presence of the teacher (2)
see
http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti
Thursday November 15, 2018 (lessons 32,5-35):
The minimum energy broadcast i.e. the minimum spanning tree (2)
- The MST problem
- Kruskal algorithm
- Prim algorithm
- Boruvka algorithm
- the Min Broadcast broblem
- MST euristic
- SPT euristic
- BAIP euristic
- approximation ratio for SPT
Tuesday November 20, 2018 (lessons 35-37,5):
The data mule problem i.e. the TSP
- (Fixed) sensor networks
- The Data Mule problem
- The TSP
- NP-completeness
- inapproximability
- special cases: metric TSP and Euclidean TSP
- generalizations
Thursday November 22, 2018 (lessons 37,5-40):
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 a bipartite graphs
- maximum matching in a bipartite graph
- P. Hall theorem (with proof)
- corollary to the P. Hall theorem
- searching an augmenting path
- Berge theorem on the augmenting paths
- algorithm based on Berge theorem
- Hopcroft & Karp algorithm
Tuesday November 27, 2018:
NO LESSON
Thursday November 29, 2018 (lessons 40-42,5):
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (2)
- Minimum weight perfect matching in bipartite graphs
- augmenting paths
- an algorithm based on searching augmenting paths
- ILP formulation
- Maximum matching in general graphs
- blossoms
- lemma on the cycle contraction
- Edmonds algorithm (idea)
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (1)
- The problem
- A Possible Approach: Virtual Forces
- A Protocol Based on Voronoi Diagrams
EVALUATION OF THE COURSE
Tuesday December 4, 2018 (lessons 42,5-45):
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)
- Voronoi Diagrams
- hypthesis of general position
- properties
- complexity
- the dual problem: Delaunay triangulation
- Algorithms to compute the Voronoi diagram
- half-plane intersection (divide et impera)
- Fortune's algorithm
Thursday December 6, 2018 (lessons 45-47,5):
Distributed Deployment 2
Tuesday December 11, 2018 (lessons 47,5-50):
Student Lessons with the presence of the teacher (3)
see
http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti
Thursday December 13, 2018 (lessons 50-52,5):
UAVs 1
Tuesday December 18, 2018 (lessons 52,5-55):
UAVs 2 (Prof. S. Silvestri - University of Kentucky Computer Science)
Tuesday December 20, 2018 (lessons 55-57,5):
Student Lessons with the presence of the teacher (4)
see
http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti
Lesson Diary A.y. 2017-2018
Friday September 29, 2017 (Lessons 1-2,5):
Introduction
The Routing Problem i.e. the Shortest Path Problem (1)
- The routing Problem
- The shortest path Problem (1)
- shortest paths: BFS
- the negative cycle issue
- least cost paths: introduction
Monday October 2, 2017 (Lessons 2,5-5):
The Routing Problem i.e. the Shortest Path Problem (2)
- The shortest path Problem (2)
- least cost paths (cnt.d): * Bellman-Ford algorithm
- Dijkstra algorithm
- Floyd-Warshall algorithm
- The Routing Problem on Interconnection Topologies (1)
- 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
- the Benes network
Friday October 6, 2017 (Lessons 5-7,5):
The Routing Problem i.e. the Shortest Path Problem (3)
- The Routing Problem on Interconnection Topologies (2)
- routing on the Benes network: the looping algorithm
The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (1)
- The Thompson model
- The orthogonal grid drawing of graphs
- Collinear Layout of the Complete network
- Layout of the Complete network
Monday October 9, 2017 (lessons 7,5-10):
The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)
- Layout of the Butterfly network (1)
- the Wise layout
- the Even & Even layout
- comparison between the two methods
Friday October 13, 2017 (lessons 10-12,5):
The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (3)
- Layout of the Hypercube network
- Collinear layout
- general layout
- The 3D layout problem
Monday October 16, 2017 (lessons 12,5-15):
The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem
- 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 with vertex cover
- another approximation algorithm
- Konig-Egevary theorem
The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem (1)
- The problem of minimizing boolean functions
- Model of the problem on graphs: the Minimum Set Covering Problem
- definition
- ILP formulation
- relation with the Minimum Vertex Covering Problem
- an O(log n)-approximation algorithm
Friday October 20, 2017 (lessons 15-17,5):
The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem (2)
-
- another approximation algorithm
- some related problems
- Hitting set problem
- Edge Cover problem
- Set Packing problem
- Exact Cover problem
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1)
- Introduction to the frequency assignment problems
- Direct and hidden collisions, interference graph
- L(h,k)-labeling and minimum span
- The special case h=k in relation to the suqre of a graph
- Properties of the L(h,k)-labeling and their proofs
Monday October 23, 2017 (lessons 17.5-20):
Student Lessons with the presence of the teacher (1)
see
http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti
Friday October 27, 2017 (lessons 20-22.5):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)
-
- Proof of NP-completeness for diameter 2 graphs
- Lower bound of Delta+1 on lambbda
- 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
- Approximate results: outerplanar graphs
Monday October 30, 2017 (lessons 22.5-25):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)
- variations of the problem:
- oriented L(2,1)-labeling
- L(h1, ..., hk)-labeling
- backbone coloring
- multiple L(h,k)-labeling
- frequency assignment in GSM networks
- a parenthesis on the 4 color theorem
The minimum energy broadcast i.e. the minimum spanning tree (1)
- the Min Broadcast problem
- NP-completeness and inapproximability results (reduction from Min Set Cover)
- Relation between Min Broadcast and Min Spanning Tree (MST)
Friday November 3, 2017 (lessons 25-27.5):
The minimum energy broadcast i.e. the minimum spanning tree (2)
- The MST problem
- Kruskal algorithm
- Prim algorithm
- Boruvka algorithm
- the Min Broadcast broblem
- MST euristic
- SPT euristic
- BAIP euristic
- approximation ratio for SPT
Monday November 6, 2017 (lessons 27.5-30):
The data mule problem i.e. the TSP
- (Fixed) sensor networks
- The Data Mule problem
- The TSP
- NP-completeness
- inapproximability
- special cases: metric TSP and Euclidean TSP
- generalizations
Friday November 10, 2017 (lessons 30-32.5):
Attendance at the Workshop in honour of Janos Korner (both students and teacher)
Monday November 13, 2017 (lessons 32.5-35):
Student Lessons with the presence of the teacher (2)
see
http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti
Friday November 17, 2017 (lessons 35-37.5):
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 a bipartite graphs
- maximum matching in a bipartite graph
- P. Hall theorem (with proof)
- corollary to the P. Hall theorem
- searching an augmenting path
- Berge theorem on the augmenting paths
- algorithm based on Berge theorem
- Hopcroft & Karp algorithm
Monday November 20, 2017 (lessons 37.5-40):
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (2)
- Minimum weight perfect matching in bipartite graphs
- augmenting paths
- an algorithm based on searching augmenting paths
- ILP formulation
- Maximum matching in general graphs
- blossoms
- lemma on the cycle contraction
- Edmonds algorithm (idea)
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (1)
- The problem
- A Possible Approach: Virtual Forces
EVALUATION OF THE COURSE
Friday November 24, 2017 (lessons 40-42.5):
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)
- A Protocol Based on Voronoi Diagrams
- Voronoi Diagrams
- hypthesis of general position
- properties
- complexity
- the dual problem: Delaunay triangulation
- Algorithms to compute the Voronoi diagram
- half-plane intersection (divide et impera)
- Fortune's algorithm
Monday November 27, 2017 (lessons 42.5-45):
Student Lessons with the presence of the teacher (3)
see
http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti
Friday December 1, 2017 (lessons 45-47.5):
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (3)
- Heterogeneous sensors
- A new notion of distance: Laguerre distance
- Voronoi-Laguerre diagrams
- A protocol based on Voronoi-Laguerre distance
Monitoring by UAVs i.e. What? (1)
Some theses proposals
Monday December 4, 2017 (lessons 47.5-50):
IT Meeting -
http://www.studiareinformatica.uniroma1.it/38-it-meeting-lunedi-4-dicembre-2017
Friday December 8, 2017:
Holiday
Monday December 11, 2017 (lessons 50-52.5):
Monitoring by UAVs i.e. What? (2)
Some theses proposals
Some problems in (co-)Phylogeny
Some other theses proposals
Friday December 15, 2017 (lessons 52.5-55):
Student Lessons with the presence of the teacher (4)
see
http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti
Monday December 18, 2017 (lessons 55-57.5):
Student Lessons with the presence of the teacher (5)
see
http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti
Friday December 22, 2017 (lessons 57.5-60):
Mid term exam
Previous years' Diaries
Lesson Diary A.y. 2016-2017
Monday September 26, 2016 (Lessons 1-2):
Introduction
The Routing Problem i.e. the Shortest Path Problem (1)
- The routing Problem
- The shortest path Problem (1)
- shortest paths: BFS
- the negative cycle issue
- least cost paths: introduction * Bellman-Ford algorithm
Friday September 30, 2016 (Lessons 3-4):
The Routing Problem i.e. the Shortest Path Problem (2)
- The shortest path Problem (2)
- least cost paths (cnt.d):
- Dijkstra algorithm
- Floyd-Warshall algorithm
- The Routing Problem on Interconnection Topologies (1)
- the packet switching model
- the Butterfly network
Monday October 3, 2016 (Lessons 5-6):
The Routing Problem i.e. the Shortest Path Problem (3)
- The Routing Problem on Interconnection Topologies (2)
- routing on the Butterfly network: the greedy algorithm
- the concept of blocking network, non-blocking network and rearrangeable network
- 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)
- The Thompson model
- The orthogonal grid drawing of graphs
- Collinear Layout of the Complete network
- Layout of the Complete network
Friday October 7, 2016 (lessons 7-8):
The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)
- Layout of the Butterfly network (1)
- the Wise layout
- the Even & Even layout
- comparison between the two methods
Monday October 10, 2016 (lessons 9-10):
The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (3)
- Layout of the Butterfly network (2)
- Optimal area Layout of the Butterfly
- Layout of the Hypercube network
- Collinear layout
- general layout
- The 3D layout problem
Friday October 14, 2016 (lessons 11-12):
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 with vertex cover
- another approximation algorithm
Monday October 17, 2016 (lessons 13-14):
The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (2)
- minimum vertex cover (cntd)
The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem (1)
- The problem of minimizing boolean functions
- Model of the problem on graphs: the Minimum Set Covering Problem
- definition
- ILP formulation
- relation with the Minimum Vertex Covering Problem
- an O(log n)-approximation algorithm
- another approximation algorithm
Friday October 21, 2016 (lessons 15-16):
The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem (2)
-
- some related problems
- Hitting set problem
- Edge Cover problem
- Set Packing problem
- Exact Cover problem
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1)
- Introduction to the frequency assignment problems
- Direct and hidden collisions, interference graph
Monday October 24, 2016 (lessons 17-18):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)
- L(h,k)-labeling and minimum span
- The special case h=k in relation to the suqre of a graph
- Properties of the L(h,k)-labeling and their proofs
- Proof of NP-completeness for diameter 2 graphs
- Lower bound of Delta+1 on lambbda
- Exemple: a graph requiring lambda=Delta squared - Delta
Friday October 28, 2016 (lessons 19-20):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)
- L(h,k)-labeling and minimum span (cntd)
- 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
- Approximate results: outerplanar graphs (part)
Monday October 31, 2016 (lessons 21-22):
No lessons, due to security check after the earthquacke of October 30.
Friday November 4, 2016 (lessons 23-24):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (4)
- L(h,k)-labeling and minimum span (cntd) * Approximate results: outerplanar graphs (part)
- variations of the problem:
- oriented L(2,1)-labeling
- L(h1, ..., hk)-labeling
- backbone coloring
- multiple L(h,k)-labeling
- frequency assignment in GSM networks
- a parenthesis on the 4 color theorem
Monday November 7, 2016 (lessons 25-26):
Mid term evaluation (part 1).
Friday November 11, 2016 (lessons 27-28):
Mid term evaluation (part 2).
Monday November 14, 2016 (lessons 29-30):
The minimum energy broadcast i.e. the minimum spanning tree (1)
- the Min Broadcast problem
- NP-completeness and inapproximability results (reduction from Min Set Cover)
- Relation between Min Broadcast and Min Spanning Tree (MST)
Friday November 18, 2016 (lessons 31-32):
The minimum energy broadcast i.e. the minimum spanning tree (2)
- The MST problem
- Kruskal algorithm
- Prim algorithm
- Boruvka algorithm
- the Min Broadcast broblem
- MST euristic
- SPT euristic
- BAIP euristic
- approximation ratio for SPT
Monday November 21, 2016 (lessons 33-34):
The data mule problem i.e. the TSP
- (Fixed) sensor networks
- The Data Mule problem
- The TSP
- NP-completeness
- inapproximability
- special cases: metric TSP and Euclidean TSP
- generalizations
Friday November 25, 2016 (lessons 35-36):
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 a bipartite graphs
- maximum matching in a bipartite graph
- P. Hall theorem (with proof)
- corollary to the P. Hall theorem
- searching an augmenting path
- Berge theorem on the augmenting paths
Monday November 28, 2016 (lessons 37-38):
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (2)
-
- algorithm based on Berge theorem
- Hopcroft & Karp algorithm
- Minimum weight perfect matching in bipartite graphs
- augmenting paths
- an algorithm based on searching augmenting paths
- ILP formulation
- Maximum matching in general graphs
- blossoms
- lemma on the cycle contraction
- Edmonds algorithm (idea)
Friday December 2, 2016 (lessons 39-40):
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (1)
- The problem
- A Possible Approach: Virtual Forces
- A Protocol Based on Voronoi Diagrams
- Voronoi Diagrams
- hypthesis of general position
- properties
- complexity
- the dual problem: Delaunay triangulation
- Algorithms to compute the Voronoi diagram
- half-plane intersection (divide et impera)
Monday December 5, 2016 (lessons 41-42):
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)
- Algorithms to compute the Voronoi diagram (cntd)
- Heterogeneous sensors
- A new notion of distance: Laguerre distance
- Voronoi-Laguerre diagrams
- A protocol based on Voronoi-Laguerre distance
Friday December 9, 2016 (lessons 43-44):
No lesson: the building is closed
Monday December 12, 2016 (lessons 45-46):
Student lessons
Friday December 16, 2016 (lessons 47-48):
IT meeting
Monday December 19, 2016 (lessons 49-50):
Student lessons
Tuesday December 20, 2016 (lessons 51-52):
Student lessons
Lesson Diary A.y. 2015-2016
Tuesday September 22, 2015 (Lessons 1-2):
Introduction
The Routing Problem i.e. the Shortest Path Problem (1)
- The routing Problem
- The shortest path Problem (1)
- shortest paths: BFS
- the negative cycle issue
- least cost paths: introduction
Friday September 25, 2015 (Lessons 3-4):
The Routing Problem i.e. the Shortest Path Problem (2)
- The shortest path Problem (2)
- least cost paths (cnt.d):
- Bellman-Ford algorithm
- Dijkstra algorithm
- Floyd-Warshall algorithm
- The Routing Problem on Interconnection Topologies (1)
- the packet switching model
- the Butterfly network
- routing on the Butterfly network: the greedy algorithm
Tuesday September 29, 2015 (Lessons 5-6):
The Routing Problem i.e. the Shortest Path Problem (3)
- The Routing Problem on Interconnection Topologies (2)
- the concept of blocking network, non-blocking network and rearrangeable network
- 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)
- The Thompson model
- The orthogonal grid drawing of graphs
- Collinear Layout of the Complete network
Friday October 2, 2015 (lessons 7-8):
The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)
- Layout of the Complete network
- Layout of the Butterfly network
Friday October 2, 2015 (lessons 9-10):
The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (3)
- Layout of the Butterfly network (3)
- the Even & Even layout
- comparison between the two methods
Tuesday October 6, 2015 (lessons 11-12):
The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (4)
- Layout of the Butterfly network (4)
- Optimal area Layout of the Butterfly
- Layout of the Hypercube network
- The 3D layout problem
Tuesday October 9, 2015 (lessons 13-14):
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 with vertex cover
Tuesday October 13, 2015 (lessons 15-16):
The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (2)
- minimum vertex cover (cntd)
- another approximation algorithm
- Konig-Egevary theorem
The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem
- The problem of minimizing boolean functions
- Model of the problem on graphs: the Minimum Set Covering Problem
- definition
- ILP formulation
- relation with the Minimum Vertex Covering Problem
- an O(log n)-approximation algorithm
- another approximation algorithm
- some related problems
- Hitting set problem
- Edge Cover problem
- Set Packing problem
- Exact Cover problem
Tuesday October 20, 2015 (lessons 17-18):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1)
- Introduction to the frequency assignment problems
- Direct and hidden collisions, interference graph
- L(h,k)-labeling and minimum span
- The special case h=k in relation to the suqre of a graph
- Properties of the L(h,k)-labeling and their proofs
- Proof of NP-completeness for diameter 2 graphs
Friday October 23, 2015 (lessons 19-20):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)
- L(h,k)-labeling and minimum span (cntd.)
- Lower bound of Delta+1 on lambbda
- Exemple: 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
Tuesday October 27, 2015 (lessons 21-22):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)
- L(h,k)-labeling and minimum span (cntd.)
- Approximate results: outerplanar graphs
- variations of the problem:
- oriented L(2,1)-labeling
- L(h1, ..., hk)-labeling
- backbone coloring
- multiple L(h,k)-labeling
- frequency assignment in GSM networks
- a parenthesis on the 4 color theorem
Friday October 30, 2015 (lessons 23-24):
The minimum energy broadcast i.e. the minimum spanning tree (1)
Friday November 6, 2015:
Mid term exam
Tuesday November 10, 2015 (lessons 25-26):
The minimum energy broadcast i.e. the minimum spanning tree (2)
- the Min Broadcast broblem
- MST euristic
- SPT euristic
- BAIP euristic
- approximation ratio for SPT
Friday November 13, 2015 (lessons 27-28):
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (1)
- the problem of centralized deployment
- the problem on graphs: min weight matching in a bipartite graphs
- maximum matching in a bipartite graph
- P. Hall theorem (with proof)
- corollary to the P. Hall theorem
- searching an augmenting path
- Berge theorem on the augmenting paths
Tuesday November 17, 2015 (lessons 29-30):
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (2)
-
- algorithm based on Berge theorem
- Hopcroft & Karp algorithm
- Minimum weight perfect matching in bipartite graphs
- augmenting paths
- an algorithm based on searching augmenting paths
- ILP formulation
- Maximum matching in general graphs
- blossoms
- lemma on the cycle contraction
- Edmonds algorithm (idea)
Friday November 20, 2015 (lessons 31-32):
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (1)
- The problem
- A Possible Approach: Virtual Forces
- A Protocol Based on Voronoi Diagrams
- Voronoi Diagrams
- hypthesis of general position
- properties
- complexity
- the dual problem: Delaunay triangulation
- Algorithms to compute the Voronoi diagram
- half-plane intersection (divide et impera)
Tuesday November 24, 2015 (lessons 33-34):
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)
- Algorithms to compute the Voronoi diagram (cntd)
- Heterogeneous sensors
- A new notion of distance: Laguerre distance
- Voronoi-Laguerre diagrams
- A protocol based on Voronoi-Laguerre distance
Lesson Diary A.y. 2014-2015
Tuesday September 29, 2014 (Lessons 1-2):
Introduction
The Routing Problem i.e. the Shortest Path Problem (1)
- The routing Problem
- The shortest path Problem (1)
- shortest paths: BFS
- least cost paths: introduction
Friday October 3, 2014 (Lessons 3-4):
The Routing Problem i.e. the Shortest Path Problem (2)
- The shortest path Problem (2)
- least cost paths (cnt.d):
- Bellman-Ford algorithm
- Dijkstra algorithm
- Floyd-Warshall algorithm
- The Routing Problem on Interconnection Topologies (1)
- the packet switching model
- the Butterfly network
- routing on the Butterfly network: the greedy algorithm
Tuesday October 7, 2014 (Lessons 5-6):
The Routing Problem i.e. the Shortest Path Problem (3)
- The Routing Problem on Interconnection Topologies (2)
- the concept of blocking network, non-blocking network and rearrangeable network
- 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)
- The Thompson model
- The orthogonal grid drawing of graphs
- Layout of the Butterfly network (1)
Friday October 10, 2014 (lessons 7-8):
The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)
- Layout of the Butterfly network (2)
- the Wise layout
- the Even & Even layout
- comparison between the two methods
Tuesday October 14, 2014 (lessons 9-10):
The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (3)
- Layout of the Butterfly network (3)
- Optimal area Layout of the Butterfly
- Layout of the Hypercube network
- The 3D layout problem
Tuesday October 17, 2014 (lessons 11-12):
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 in relation with vertex cover
Tuesday October 21, 2014 (lessons 13-14):
The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (2)
- minimum vertex cover (cnt.d)
- matching in relation with vertex cover
- another approximation algorithm
- Konig-Egevary theorem
The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem
- The problem of minimizing boolean functions
- Model of the problem on graphs: the Minimum Set Covering Problem
- definition
- ILP formulation
- relation with the Minimum Vertex Covering Problem
- an O(log n)-approximation algorithm
- another approximation algorithm
- some related problems
- Hitting set problem
- Edge Cover problem
- Set Packing problem
- Exact Cover problem
Friday October 24, 2014:
No lesson because of bus and train strike
Tuesday October 28, 2014 (lessons 15-16):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1)
- Introduction to the frequency assignment problems
- Direct and hidden collisions, interference graph
- L(h,k)-labeling and minimum bandwidth
- The special case h=k in relation to the suqre of a graph
- Properties of the L(h,k)-labeling and their proofs
Friday October 31, 2014 (lessons 17-18):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)
- L(h,k)-labeling and minimum bandwidth (cntd.)
- Proof of NP-completeness for diameter 2 graphs
- Lower bound of Delta+1 on lambbda
- Exemple: 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
Tuesday November 4, 2014 (lessons 19-20):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)
- L(h,k)-labeling and minimum bandwidth (cntd.)
- Exact results: paths
- Exact results: cycles
- Approximate results: outerplanar graphs
- variations of the problem:
- oriented L(2,1)-labeling
- L(h1, ..., hk)-labeling
- backbone coloring
- multiple L(h,k)-labeling
Friday November 7, 2014 (lessons 21-22):
Mid term exam
Tuesday November 11, 2014 (lessons 23-24):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (4)
* variations of the problem (cnt.d):
-
- frequency assignment in GSM networks
- a parenthesis on the 4 color theorem
The minimum energy broadcast i.e. the minimum spanning tree (1)
Friday November 14, 2014 (lessons 25-26):
The minimum energy broadcast i.e. the minimum spanning tree (2)
- the Min Broadcast broblem
- MST euristic
- SPT euristic
- BAIP euristic
Tuesday November 18, 2014 (lessons 27-28):
The minimum energy broadcast i.e. the minimum spanning tree (3)
- the Min Broadcast broblem (cnt.d)
- approximation ratio for SPT
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (1)
- the problem of centralized deployment
- Ithe problem on graphs: min weight matching in a bipartite graphs
- maximum matching in a bipartite graph
- P. Hall theorem (with proof)
- corollary to the P. Hall theorem
Friday November 21, 2014 (lessons 29-30):
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (2)
- Maximum matching in bipartite graphs
- searching an augmenting path
- Berge theorem on the augmenting paths
- algorithm based on Berge theorem
- Hopcroft & Karp algorithm
- Minimum weight perfect matching in bipartite graphs
- augmenting paths
- an algorithm based on searching augmenting paths
- ILP formulation
- Maximum matching in general graphs
- blossoms
- lemma on the cycle contraction
- Edmonds algorithm (idea)
Tuesday November 25, 2014 (lessons 31-32):
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (1)
- The problem
- A Possible Approach: Virtual Forces
- A Protocol Based on Voronoi Diagrams
- Voronoi Diagrams
- hypthesis of general position
- properties
- complexity
- the dual problem: Delaunay triangulation
- Algorithms to compute the Voronoi diagram
- half-plane intersection (divide et impera)
Friday November 28, 2014 (lessons 33-34):
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)
- Algorithms to compute the Voronoi diagram (cnt.d)
- Heterogeneous sensors
- A new notion of distance: Laguerre distance
Tuesday December 2, 2014 (lessons 35-36):
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (3)
- Voronoi-Laguerre diagrams
- A protocol based on Voronoi-Laguerre distance
Friday December 5, 2014 (lessons 37-38):
Student lessons (1)
Tuesday December 9, 2014 (lessons 39-40):
Student lessons (2)
Tuesday December 16, 2014 (lessons 41-42):
Student lessons (3)
Lesson Diary A.y. 2013-2014
Monday September 30, 2013 (Lessons 1-2):
Introduction
The Routing Problem i.e. the Shortest Path Problem (1)
- The routing Problem
- The shortest path Problem (1)
- shortest paths: BFS
- least cost paths:
- Bellman-Ford algorithm
- Dijkstra algorithm
Friday October 4, 2013 (lessons 3-4):
The Routing Problem i.e. the Shortest Path Problem (2)
- The shortest path Problem (2)
- least cost paths (cntd.):
- 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
- the Benes network
- routing om the Benes network: the looping algorithm
Monday October 7, 2013 (lessons 5-6):
The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (1)
- The Thompson model
- The orthogonal grid drawing of graphs
- Layout of the Butterfly network (1)
- the Wise layout
- the Even & Even layout
Friday October 11, 2013 (lessons 7-8):
The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)
- Layout of the Butterfly network (2)
- Overview of other results
- Optimal area Layout of the Butterfly
- Layout of the Hypercube network
- The 3D layut problem
Monday October 14, 2013 (lessons 9-10):
The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (1)
- The problem
- worms
- damages caused by worms
- worm expansion
- Model of the problem on graphs
- minimum vertex cover
- definition
- ILP model
- a 2-approximation algorithm
- independent set in relation with vertex cover
- matching in relation with vertex cover
- another approximation algorithm
Friday October 18, 2013 (lessons 11-12):
The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (2)
- minimum vertex cover (cntd.)
The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem
- The problem of minimizing boolean functions
- Its equivalence with the Minimum Set Covering Problem
- the Minimum Set Covering Problem
- definition
- ILP formulation
- relation with the Minimum Vertex Covering Problem
- an O(log n)-approximation algorithm
- another approximation algorithm
- some related problems
- Hitting set problem
- Edge Cover problem
- Set Packing problem
- Exact Cover problem
Monday October 21, 2013 (lessons 13-14):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1)
- Introduction to the frequency assignment problems
- Direct and hidden collisions, interference graph
- L(h,k)-labeling and minimum bandwidth
- The special case h=k in relation to the suqre of a graph
- Properties of the L(h,k)-labeling and their proofs
- Proof of NP-completeness for diameter 2 graphs
Friday October 25, 2013 (lessons 15-16):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)
- L(h,k)-labeling and minimum bandwidth (cntd.)
- Lower bound of Delta+1 on lambbda
- Exemple: 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
Monday October 28, 2013 (lessons 17-18):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)
- L(h,k)-labeling and minimum bandwidth (cntd.)
- Approximate results: outerplanar graphs
- variations of the problem:
- oriented L(2,1)-labeling
- L(h1, ..., hk)-labeling
- backbone coloring
- multiple L(h,k)-labeling
- frequency assignment in GSM networks
- a parenthesis on the 4 color theorem
Monday November 4, 2013 (lessons 19-20):
The minimum energy broadcast i.e. the minimum spanning tree (1)
Friday November 8, 2013 (lessons 21-22):
The minimum energy broadcast i.e. the minimum spanning tree (2)
- the Min Broadcast broblem
- MST euristic
- SPT euristic
- BAIP euristic
- approximation ratio for SPT
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (1)
- the problem of centralized deployment
- Ithe problem on graphs: min weight matching in a bipartite graphs
- maximum matching in a bipartite graph
- P. Hall theorem (with proof)
- corollary to the P. Hall theorem
week November 11-15: No classes - midterm exams
Monday November 18, 2013 (lessons 23-24):
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (2)
- Maximum matching in bipartite graphs
- searching an augmenting path
- Berge theorem on the augmenting paths
- algorithm based on Berge theorem
- Hopcroft & Karp algorithm
- Minimum weight perfect matching in bipartite graphs
- augmenting paths
- an algorithm based on searching augmenting paths
- ILP formulation
- Maximum matching in general graphs
- blossoms
- lemma on the cycle contraction
- Edmonds algorithm
Friday November 22, 2013 (lessons 25-26):
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (1)
- The problem
- A Possible Approach: Virtual Forces
- A Protocol Based on Voronoi Diagrams
- Voronoi Diagrams
- hypthesis of general position
- properties
- complexity
- the dual problem: Delaunay triangulation
- Algorithms to compute the Voronoi diagram
- half-plane intersection (divide et impera)
Monday December 2, 2013 (lessons 27-28):
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)
- Algorithms to compute the Voronoi diagram (cnt.d)
Friday December 6, 2013 (lessons 29-30):
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (3)
- Heterogeneous sensors
- A new notion of distance: Laguerre distance
- Voronoi-Laguerre diagrams
- A protocol based on Voroi-Laguerre distance
Monday December 9, 2013 (lessons 31-32):
Student Lessons
Friday December 13, 2013 (lessons 33-34):
Student Lessons
Monday December 16, 2013 (lessons 35-36):
Student Lessons
Diario delle Lezioni A.A. 2012-2013
Mercoledi' 3 Ottobre 2011 (Ore 1-2):
Introduzione al Corso
Il Problema dell'Instradamento ovvero il Cammino più Corto o di Costo minimo (1)
- Il problema dell'instradamento
- Il problema del cammino di costo minimo
- cammini piu' corti: visita in ampiezza
- cammini minimi:
- algoritmo di Bellman-Ford
Lunedi' 8 Ottobre 2012 (Ore 3-4):
Il Problema dell'Instradamento ovvero il Cammino più Corto o di Costo minimo (2)
-
- cammini minimi (segue):
- algoritmo di Dijkstra
- algoritmo di Floyd-Warshall
- Instradamento sulle Topologie di Interconnessione
- il modello di packet switching
- la Butterfly
- instradamento sulla Butterfly
Mercoledi' 10 Ottobre 2012 (Ore 5-6):
Il Problema dell'Instradamento ovvero il Cammino più Corto o di Costo minimo (3)
-
- concetto di rete bloccante, di rete non bloccante e di rete riarrangabile
- la Benes
- looping algorithm e instradamento sulla Benes
Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (1)
- Il modello di Thompson
- Il disegno ortogonale di grafi su griglia
- Il layout della Butterfly
Lunedi' 15 Ottobre 2012 (Ore 7-8):
Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (2)
- Il layout della Butterfly (segue)
- il layout di Even ed Even
- panoramica di altri risultati
- Layout della butterfly di area ottima
Mercoledi' 17 Ottobre 2012 (Ore 9-10):
Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (3)
- Il layout dell'ipercubo
- il problema del layut 3D
Il Problema di infettare (e difendere) una rete con un Worm ovvero la Minima Copertura di Nodi (1)
- Il problema
- i worm
- danni causati dai worm
- diffusione dei worm
Lunedi' 22 Ottobre 2012 (Ore 11-12):
Il Problema di infettare (e difendere) una rete con un Worm ovvero la Minima Copertura di Nodi (2)
- Modello del problema su grafi
- la minima copertura di nodi
- definizione
- un algoritmo 2-approssimante
- insieme indipendente e sua relazione con la copertura di nodi
- accoppiamento e sua relazione con la copertura di nodi
- un ulteriore algoritmo approssimante
- teorema di Konig-Egevary
Mercoledi' 24 Ottobre 2012 (Ore 13-14):
Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (1)
- Introduzione ai problemi di assegnazione di frequenze
- Collisioni dirette, collisioni nascoste e grafo delle interferenze
- L(h,k)-etichettatura e minima banda
- Il caso speciale h=k in relazione al quadrato di un grafo
Lunedi' 29 Ottobre 2012 (Ore 15-16):
Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (2)
- L(h,k)-etichettatura (segue)
- Dimostrazione delle proprietà della L(h,k)-etichettatura (h e k primi tra loro ed interi)
- Dimostrazione della NP-completezza per grafi di diametro 2
- Limitazione inferiore di Delta+1 su lambbda
- Esempio di grafo che richiede lambda=Delta quadro - Delta
- Limitazione superiore di Delta quadro + 2 Delta
- Congettura di Griggs e Yeh
- Risultati esatti: clicche
Lunedi' 5 Novembre 2012 (Ore 17-18):
Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (3)
- L(h,k)-etichettatura (segue)
- Risultati esatti: clicche
- Risultati esatti: stelle
- Risultati esatti: alberi
- Risultati esatti: cammini
- Risultati esatti: cicli
Mercoledi' 7 Novembre 2012 (Ore 19-20):
Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (4)
- L(h,k)-etichettatura (segue)
-
- Risultati approssimati: grafi outerplanar
- varianti del problema:
- L(2,1)-etichettatura orientata
- L(h1, ..., hk)-etichettatura
- backbone coloring
- L(h,k)-etichettatura multipla
- assegnazione di frequenze in reti GSM
- una divagazione sul teorema dei 4 colori
Il Problema del Broadcast con minimo dispendio di energia ovvero il Minimo Albero Ricoprente (1)
12-15 Novembre 2012: settimana di interruzione della didattica
Lunedi' 19 Novembre 2012 (Ore 21-22):
Il Problema del Broadcast con minimo dispendio di energia ovvero il Minimo Albero Ricoprente (2)
- Relazione tra MinBroadcast e MinSpanningTree
- Il problema del Minimo Albero Ricoprente
- Algoritmo di Kruskal
- Algoritmo di Prim
- Algoritmo di Boruvka
- Il problema del Min Broadcast
- Euristica MST
- Euristica SPT
- Euristica BAIP
- fattore di approssimazione per SPT
Mercoledi' 21 Novembre 2012 (Ore 23-24):
Il Problema del Dispiegamento centralizzato di Sensori Mobili ovvero il Minimo Accoppiamento Bipartito (1)
- Il problema del Dispiegamento centralizzato
- Il problema modellato sui grafi: accoppiamento bipartito di peso minimo
- Accoppiamento massimo in grafi bipartiti
- teorema di P. Hall (dimostrazione)
- corollario del th. di P. Hall (dim.)
- equivalenza con il problema del minimo flusso
- cammini aumentanti
Lunedi' 26 Novembre 2012 (Ore 25-26):
Il Problema del Dispiegamento Centralizzato di Sensori Mobili ovvero il Minimo Accoppiamento Bipartito (2)
- Accoppiamento massimo in grafi bipartiti
- teorema del cammino aumentante di Berge (dim.)
- il problema della ricerca di un camino aumentante
- algoritmo basato sul th. di Berge
- l'algoritmo di Hopcroft e Karp
- Accoppiamento perfetto di peso minimo in grafi bipartiti
- cammini aumentanti
- un algoritmo basato sui cammini aumentanti
- formulazione del problema come programmazione lineare
- Accoppiamento massimo in grafi qualunque
- boccioli (blossoms)
- lemma della contrazione dei cicli
Mercoledi' 28 Novembre 2012 (Ore 27-28):
Il Problema del Dispiegamento Centralizzato di Sensori Mobili ovvero il Minimo Accoppiamento Bipartito (3)
Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (2)
- Il problema
- L'approccio basato sulle forze virtuali
Lunedi' 3 Dicembre 2012 (Ore 29-30):
Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (2)
- L'approccio basato sui diagrammi di Voronoi
- Diagramma di Voronoi
- posizione generale
- proprieta'
- Diagramma di Voronoi
- complessita'
- Il problema duale: la triangolazione di Delaunay
- algoritmi per calcolare il diagramma di Voronoi: divide et impera
- algoritmi per calcolare il diagramma di Voronoi: sweep line (algoritmo di Fortune) - prima parte
Mercoledi' 5 Dicembre 2012 (Ore 31-32):
Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (3)
- Diagramma di Voronoi
- algoritmi per calcolare il diagramma di Voronoi: sweep line (algoritmo di Fortune) - seconda parte
- Dispiegamento con sensori eterogenei
- Distanza di Laguerre
- Diagramma di Voronoi-Laguerre
- L'approccio basato sui diagrammi di Voronoi-Laguerre
- proprieta' dell'algoritmo
Diario delle Lezioni A.A. 2011-2012
Lunedi' 3 Ottobre 2011 (Ore 1-2):
Introduzione al Corso
Il Problema dell'Instradamento ovvero il Cammino più Corto o di Costo minimo (1)
- Il problema dell'instradamento
- Il problema del cammino di costo minimo
- cammini piu' corti: visita in ampiezza
Giovedi' 6 Ottobre 2011 (Ore 3-4):
Il Problema dell'Instradamento ovvero il Cammino più Corto o di Costo minimo (2)
-
- cammini minimi:
- algoritmo di Bellman-Ford
- algoritmo di Dijkstra
- algoritmo di Floyd-Warshall
- Instradamento sulle Topologie di Interconnessione
- il modello di packet switching
- la Butterfly
- instradamento sulla Butterfly
Lunedi' 10 Ottobre 2011 (Ore 5-6):
Il Problema dell'Instradamento ovvero il Cammino più Corto o di Costo minimo (3)
-
- concetto di rete bloccante, di rete non bloccante e di rete riarrangabile
- la Benes
- looping algorithm e instradamento sulla Benes
Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (1)
- Il modello di Thompson
- Il disegno ortogonale di grafi su griglia
Mercoledi' 12 Ottobre 2011 (Ore 7-8):
Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (2)
- Il layout della Butterfly
- il layout di Wise
- il layout di Even ed Even
- panoramica di altri risultati
Lunedi' 17 Ottobre 2011 (Ore 9-10):
Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (3)
- Layout della butterfly di area ottima
- Layout tridimensionale dell'ipercubo
- il problema del layut 3D
- l'ipercubo
- cenni sul layout dell'ipercubo e sulla limitazione inferiore
Mercoledi' 19 Ottobre 2011 (Ore 11-12):
Il Problema di infettare (e difendere) una rete con un Worm ovvero la Minima Copertura di Nodi
- Il problema
- i worm
- danni causati dai worm
- diffusione dei worm
- Modello del problema su grafi
- la minima copertura di nodi
- definizione
- un algoritmo 2-approssimante
- insieme indipendente e sua relazione con la copertura di nodi
- accoppiamento e sua relazione con la copertura di nodi
- un ulteriore algoritmo approssimante
- teorema di Konig-Egevary
Lunedi' 24 Ottobre 2011 (Ore 13-14):
Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (1)
- Introduzione ai problemi di assegnazione di frequenze
- Collisioni dirette, collisioni nascoste e grafo delle interferenze
- L(h,k)-etichettatura e minima banda
- Il caso speciale h=k in relazione al quadrato di un grafo
- Dimostrazione delle proprietà della L(h,k)-etichettatura (h e k primi tra loro ed interi)
Mercoledi' 26 Ottobre 2011 (Ore 15-16):
Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (2)
- L(h,k)-etichettatura (segue)
- Dimostrazione della NP-completezza per grafi di diametro 2
- Limitazione inferiore di Delta+1 su lambbda
- Esempio di grafo che richiede lambda=Delta quadro - Delta
- Limitazione superiore di Delta quadro + 2 Delta
- Congettura di Griggs e Yeh
- Risultati esatti: clicche
- Risultati esatti: stelle
- Risultati esatti: alberi
Mercoledi' 9 Novembre 2011 (Ore 17-18):
Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (3)
- L(h,k)-etichettatura (segue)
- Risultati esatti: cammini
- Risultati esatti: cicli
- Risultati approssimati: grafi outerplanar
Lunedi' 21 Novembre 2011 (Ore 19-20):
Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (4)
* varianti del problema:
-
- L(2,1)-etichettatura orientata
- L(h1, ..., hk)-etichettatura
- backbone coloring
- L(h,k)-etichettatura multipla
- assegnazione di frequenze in reti GSM
- una divagazione sul teorema dei 4 colori
Il Problema del Broadcast con minimo dispendio di energia ovvero il Minimo Albero Ricoprente (1)
Mercoledi' 23 Novembre 2011 (Ore 21-22):
Il Problema del Broadcast con minimo dispendio di energia ovvero il Minimo Albero Ricoprente (2)
- Il problema del Minimo Albero Ricoprente
- Algoritmo di Kruskal
- Algoritmo di Prim
- Algoritmo di Boruvka
- Il problema del Min Broadcast
- Euristica MST
- Euristica SPT
- Euristica BAIP
- fattore di approssimazione per SPT
Lunedi' 28 Novembre 2010 (Ore 23-24):
Il Problema del Dispiegamento centralizzato di Sensori Mobili ovvero il Minimo Accoppiamento Bipartito (1)
- Il problema del Dispiegamento centralizzato
- Il problema modellato sui grafi: accoppiamento bipartito di peso minimo
- Accoppiamento massimo in grafi bipartiti
- teorema di P. Hall (dimostrazione)
- corollario del th. di P. Hall (dim.)
- equivalenza con il problema del minimo flusso
- cammini aumentanti
- teorema del cammino aumentante di Berge (dim.)
Mercoledi' 30 Novembre 2010 (Ore 25-26):
Il Problema del Dispiegamento centralizzato di Sensori Mobili ovvero il Minimo Accoppiamento Bipartito (2)
- Accoppiamento massimo in grafi bipartiti
- il problema della ricerca di un camino aumentante
- algoritmo basato sul th. di Berge
- l'algoritmo di Hopcroft e Karp
- Accoppiamento perfetto di peso minimo in grafi bipartiti
- cammini aumentanti
- un algoritmo basato sui cammini aumentanti
- formulazione del problema come programmazione Lineare
- Accoppiamento massimo in grafi qualunque
- boccioli (blossoms)
- lemma della contrazione dei cicli
- algoritmo di Edmonds
Lunedi' 5 Dicembre 2011 (Ore 27-28):
Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (1)
- Il problema
- L'approccio basato sulle forze virtuali
- L'approccio basato sui diagrammi di Voronoi
- Diagramma di Voronoi
- posizione generale
- proprieta'
Mercoledi' 7 Dicembre 2011 (Ore 29-30):
Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (2)
- Diagramma di Voronoi
- complessita'
- Il problema duale: la triangolazione di Delaunay
- algoritmi per calcolare il diagramma di Voronoi: divide et impera
- algoritmi per calcolare il diagramma di Voronoi: sweep line (algoritmo di Fortune)
- Dispiegamento con sensori eterogenei
- Distanza di Laguerre
- Diagramma di Voronoi-Laguerre
Lunedi' 12 Dicembre 2011 (Ore 31-32):
Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (3)
- L'approccio basato sui diagrammi di Voronoi-Laguerre
- proprieta' dell'algoritmo
Mercoledi' 14 Dicembre 2011 (Lauree)
Vacanze natalizie
Mercoledi' 11 Gennaio 2012 (Ore 33-34):
Tesine
Lunedi' 16 Gennaio 2012 (Ore 35-36):
Tesine
Mercoledi' 18 Gennaio 2012 (Ore 37-38):
Tesine
Diario delle Lezioni A.A. 2010-2011
Lunedi' 18 Ottobre 2010 (Ore 1-2):
Lectio Magistralis: Dott. Prabhakar Raghavan
Giovedi' 21 Ottobre 2010 (Ore 3-4):
Introduzione al Corso
Il Problema dell'Instradamento ovvero il Cammino più Corto o di Costo minimo (1)
- Il problema dell'instradamento
- Il problema del cammino di costo minimo
- cammini piu' corti: visita in ampiezza
- cammini minimi:
- algoritmo di Bellman-Ford
- algoritmo di Dijkstra
- algoritmo di Floyd-Warshall
Lunedi' 25 Ottobre 2010 (Ore 5-6):
Il Problema dell'Instradamento ovvero il Cammino più Corto o di Costo minimo (2)
- Instradamento sulle Topologie di Interconnessione
- il modello di packet switching
- la Butterfly
- instradamento sulla Butterfly
- concetto di rete bloccante, di rete non bloccante e di rete riarrangabile
- la Benes
- looping algorithm e instradamento sulla Benes
Giovedi' 28 Ottobre 2010 (Ore 7-8):
Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (1)
- Il modello di Thompson
- Il disegno ortogonale di grafi su griglia
- Il layout della Butterfly
- il layout di Wise
- il layout di Even ed Even
- panoramica di altri risultati
Lunedi' 1 Novembre 2010: festa
Giovedi' 4 Novembre 2010 (Ore 9-10):
Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (2)
- Layout della butterfly di area ottima
- Layout tridimensionale dell'ipercubo
- il problema del layut 3D
- l'ipercubo
- cenni sul layout e sulla limitazione inferiore
Il Problema di infettare (e difendere) una rete con un Worm ovvero la Minima Copertura di Vertici (1)
- Il problema
- i worm
- danni causati dai worm
- diffusione dei worm
Lunedi' 8 Novembre 2010 (Ore 11-12):
Il Problema di infettare (e difendere) una rete con un Worm ovvero la Minima Copertura di Nodi (2)
- Modello del problema su grafi
- la minima copertura di nodi
- definizione
- un algoritmo 2-approssimante
- insieme indipendente e sua relazione con la copertura di nodi
- accoppiamento e sua relazione con la copertura di nodi
- un ulteriore algoritmo approssimante
- teorema di Konig-Egevary
Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (1)
- Introduzione ai problemi di assegnazione di frequenze
Giovedi' 11 Novembre 2010 (Ore 13-14):
Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (2)
- Collisioni dirette, colisioni nascoste e grafo delle interferenze
- L(h,k)-etichettatura e minima banda
- Dimostrazione delle proprietà della L(h,k)-etichettatura (h e k primi tra loro ed interi)
- Il caso speciale h=k
- Dimostrazione della NP-completezza per grafi di diametro 2
- Limitazione inferiore di Delta+1 su lambbda
- Esempio di grafo che richiede lambda=Delta quadro - Delta
- Limitazione superiore di Delta quadro + 2 Delta
Lunedi' 15 Novembre 2010 (Ore 15-16):
Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (3)
- L(h,k)-etichettatura (segue)
- Congettura di Griggs e Yeh
- Risultati esatti: clicche
- Risultati esatti: stelle
- Risultati esatti: alberi
- Risultati esatti: cammini
- Risultati esatti: cicli
- Risultati approssimati: grafi outerplanar
Giovedi' 18 Novembre 2010 (Ore 17-18):
Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (4)
* L(h,k)-etichettatura (segue)
-
- Risultati approssimati: grafi outerplanar
- varianti del problema:
- L(2,1)-etichettatura orientata
- L(h1, ..., hk)-etichettatura
- backbone coloring
- assegnazione di frequenze in reti GSM
- una divagazione sul teorema dei 4 colori
Lunedi' 22 Novembre 2010 (Ore 19-20):
Il Problema del Broadcast con minimo dispendio di energia ovvero il Minimo Albero Ricoprente (1)
- Il problema del MinBroadcast
- NP-completezza e risultati di non approssimabilita' di MinBroadcast (riduzione da MinSetCover)
- Relazione tra MinBroadcast e MinSpanningTree
- Il problema del Minimo Albero Ricoprente
- Algoritmo di Kruskal
- Algoritmo di Prim
- Algoritmo di Boruvka
- Il problema del Min Broadcast
- Euristica MST
- Euristica SPT
- Euristica BAIP
- fattore di approssimazione per SPT
Giovedi' 25 Novembre 2010 (Ore 21-22):
Il Problema del Broadcast con minimo dispendio di energia ovvero il Minimo Albero Ricoprente (2)
- Il problema del Min Broadcast
- fattore di approssimazione per BAIP
- fattore di approssimazione per MST
- idea della dimostrazione della lim. sup. di 6 per MST
Il Problema del Dispiegamento centralizzato di Sensori Mobili ovvero il Minimo Accoppiamento Bipartito (1)
- Il problema del Dispiegamento centralizzato
- Il problema modellato sui grafi: accoppiamento bipartito di peso minimo
- Accoppiamento massimo in grafi bipartiti
- teorema di P. Hall (dimostrazione)
- corollario del th. di P. Hall (dim.)
- equivalenza con il problema del minimo flusso
- cammini aumentanti
- teorema del cammino aumentante di Berge (dim.)
- il problema della ricerca di un camino aumentante
- algoritmo basato sul th. di Berge
- l'algoritmo di Hopcroft e Karp
Settimana di interruzione della didattica
Lunedi' 6 Dicembre 2010 (Ore 23-24):
Il Problema del Dispiegamento centralizzato di Sensori Mobili ovvero il Minimo Accoppiamento Bipartito (2)
- Accoppiamento perfetto di peso minimo in grafi bipartiti
- cammini aumentanti
- un algoritmo basato sui cammini aumentanti
- formulazione del problema come programmazione Lineare
- Accoppiamento massimo in grafi qualunque
- boccioli (blossoms)
- lemma della contrazione dei cicli
- algoritmo di Edmonds
Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (1)
- Il problema
- L'approccio basato sulle forze virtuali
- L'approccio basato sui diagrammi di Voronoi
- Diagramma di Voronoi
- posizione generale
- proprieta'
Giovedi' 9 Dicembre 2010 (Ore 25-26):
Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (2)
- Diagramma di Voronoi
- complessita'
- Il problema duale: la triangolazione di Delaunay
- algoritmi per calcolare il diagramma di Voronoi: divide et impera
- algoritmi per calcolare il diagramma di Voronoi: sweep line (algoritmo di Fortune)
Lunedi' 13 Dicembre 2010 (Ore 27-28):
Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (3)
- Dispiegamento con sensori eterogenei
- Distanza di Laguerre
- Diagramma di Voronoi-Laguerre
- L'approccio basato sui diagrammi di Voronoi-Laguerre
- proprieta' dell'algoritmo
Giovedi' 16 Dicembre 2010 (Lauree)
Lunedi' 20 Dicembre 2010 (Incontro con le aziende)
Vacanze natalizie
Lunedi' 10 Gennaio 2011 (Ore 29-30):
Tesine
Giovedi' 13 Gennaio 2011 (Ore 31-32):
Tesine
Venerdi' 14 Gennaio 2011 (Ore 33-34):
Tesine
Lunedi' 17 Gennaio 2011 (Ore 35-36):
Tesine
Giovedi' 20 Gennaio 2011 (Ore 37-38):
Tesine
--
Tiziana Calamoneri - 2021-09-23
Comments