Tags:
create new tag
view all tags

# 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
• shortest paths: BFS
• 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
• the Wise layout

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)

• 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
• 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)
• Fortune algorithm
• 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
• shortest paths: BFS
• 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)

• 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
• 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)

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)

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)

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)
• Fortune algorithm

• 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)

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)

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)
• definition
• ILP model

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)

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)

• 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)

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
• 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)

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)

### 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)

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)

• 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
• 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):

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

### 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)
• 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
• 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)

• 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
• 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)
• Fortune's algorithm
• 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
• the Wise layout

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)

• 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)
• Fortune's algorithm
• 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)

• 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)
• Fortune's algorithm
• 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.):
• 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 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.)
• Konig-Egevary theorem
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)

• 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)
• Fortune's algorithm

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 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

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
• il layout di Wise

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)

• algoritmo di Edmonds

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 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

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 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
• 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)

• 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

--  Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy) Torna al Dipartimento di Informatica Deutsch English Español _Français_ Italiano  