ProgrammaDelCorso < Algoreti

<a href="WebHome1011" target="_self" title="Home">Home</a>

---+++ <font color="blue" size="+2"> Program and Textbooks/ Programma del corso e Testi </font>

<table align="left" border="0" style="height: 4331px; width: 1476px;"> <tbody> <tr valign="top"> <td style="padding-right: 5px;" width="50%">
---+++ <font color="blue" size="+2">English</font>
---
The general topics that will be dealt with during the course are listed here.
For a deeper detail, please go to the Lesson Diary.

*NOTE:* Papers can be freely downloaded by connecting to the Sapienza network.
Please let me know if you note that a link does not work.
---
<font color="green" size="+2">0. Introduction to the Course</font>

<font color="red" size="+2">1. cable networks</font>

<font color="blue" size="+1">
1.1. The Routing problem
i.e.
the minimum cost shortest path</font>

%RED%
References:
%ENDCOLOR%
   * [J] chap.3, excluding sect. 3.2, 3.4, 3.10 [[%ATTACHURL%/ShortestPath.pdf][download here]]
   * [CLRS] [[%ATTACHURL%/1_1_SingleSourceShortestPaths.pdf][download here]]
   * [L] sect. 3.4 pages 511-521 + pages 440-442 + 451-456 [[%ATTACHURL%/Packet-Routing_Algorithms.pdf][download here]] [[%ATTACHURL%/ButterflyBenes.pdf][...and here]] <p> </p>

%RED% Students' lessons:%ENDCOLOR%
   * [Aal14] An analysis of packet forwarding policies for maximum and average flow in a special kind of network (line network). http://link.springer.com/chapter/10.1007%2F978-3-642-54423-1_53
   * [Lal16] An efficient iterative MapReduce-like algorithm to detect connected components in large graphs. https://ieeexplore.ieee.org/document/7515231
   * [NCO13] Definition of weakly dynamic graphs, and an efficient polynomial time algorithm that computes in advance the shortest paths for all possible configurations on them [[%ATTACHURL%/Routing.pdf][download here]]
   * [W14] Energy-Efficient and Adaptive Algorithms for Constructing Multipath Routing in Wireless Sensor Networks http://link.springer.com/chapter/10.1007%2F978-3-662-44917-2_32
 <p> </p>

%RED% For a thorough examination of the topic:%ENDCOLOR%
   * Dynamic routing algorithms for interconnection topologies
   * [GR93] A heuristic improvement of the Bellman-Ford algorithm by the great researcher Andrew V. Goldberg https://www.sciencedirect.com/science/article/pii/089396599390022F
<hr />

<font color="blue" size="+1">
1.2. The layout of interconnection networks
i.e.
the orthogonal grid graph drawing</font>

%RED%
References:
%ENDCOLOR%
   * [L80] only first page [[%ATTACHURL%/HtreeLeiserson_p1.pdf][download here]]
   * [W81] only figures and related observations, [[%ATTACHURL%/Compact_Layouts_of_Banyan-FFT_Networks.pdf][download here]]
   * [EE00] excluding sect. 3.3. http://onlinelibrary.wiley.com/doi/10.1002/1097-0037%28200009%2936:2%3C91::AID-NET3%3E3.0.CO;2-4/abstract
   * [L] pages 392-396 [[%ATTACHURL%/HyperCube.pdf][download here]]
   * [YVP99] whole [[%ATTACHURL%/YVP99.pdf][download here]]
   * [YP97] sections 1 and 2 [[%ATTACHURL%/LayoutCompleto.pdf][download here]] <p> </p>

%RED% Students' lessons:%ENDCOLOR%
   * [GG01] Analysis of the layout of Hypercubes http://arxiv.org/abs/cs/0105034v1
   * [L80] The Leiserson seminal paper on the layout of complete binary trees [[%ATTACHURL%/HtreeLeiserson.pdf][download here]]
   * [Mal13] 3D interconnection networks using an efficient multicast communication protocol https://ieeexplore.ieee.org/document/6498567
   * [Xal09] A low-radix and low-diameter 3D interconnection network design https://ieeexplore.ieee.org/document/4798234
 <p> </p>

%RED% For a thorough examination of the topic:%ENDCOLOR%
   * The seminal paper by Leighton and Rosenberg: http://www.dtic.mil/dtic/tr/fulltext/u2/a143430.pdf 
   * The paper with the slanted Butterfly layout: https://www.researchgate.net/publication/220246076_A_Compact_Layout_of_the_Butterfly
<p> </p> <hr />

<font color="blue" size="+1">
1.3. The problem of infecting a network with a worm
i.e.
   the minimum vertex cover problem</font>

%RED%
References:
%ENDCOLOR%
   * http://it.wikipedia.org/wiki/Worm
   * https://pdfs.semanticscholar.org/3f2e/5b88c4b631c931f6db805f4ae3c0b531a8e8.pdf (small section on the worm)
   * http://en.wikipedia.org/wiki/Vertex_cover
   * http://en.wikipedia.org/wiki/K%C3%B6nig%27s_theorem_%28graph_theory%29
   * [CLRS] pp 875-877 [[%ATTACHURL%/1_3_VertexCover.pdf][download here]]
   * [GYnero] [[%ATTACHURL%/document.pdf][download here]] 
   * [CA23] https://ieeexplore.ieee.org/document/10296816
<p> </p>

%RED% Students' lessons:%ENDCOLOR%
   * [Aal18] https://cs.emis.de/LIPIcs/volltexte/2018/9152/pdf/LIPIcs-ICALP-2018-148_.pdf
   * [Cal14] http://link.springer.com/chapter/10.1007/978-3-662-44602-7_2
   * [Fal07] [[%ATTACHURL%/Combinatorial-Optimisation-of-Worm-Propagationon-an-Unknown-Network.pdf][Combinatorial Optimisation of Worm Propagation an Unknown Network]]
   * [KM09] https://ajc.maths.uq.edu.au/pdf/45/ajc_v45_p235.pdf (eternal VC)
   * [KM16] https://www.researchgate.net/publication/264123208_Protecting_a_Graph_with_Mobile_Guards (focus only on eternal VC)<hr />
<!--
<font color=blue size="+1"> 
1.4. The problem of minimizing a boolean circuit
i.e.
   the minimum set covering problem</font>

<font color=red>
References:
</font>
   * [CLRS] [[%ATTACHURL%/MinSetCover.pdf][download here]]
   * http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK5/NODE201.HTM
   * http://en.wikipedia.org/wiki/Set_cover_problem
   * Notes of Prof. J. Cherian, Univ. of Waterloo - Canada. http://www.math.uwaterloo.ca/~jcheriya/PS_files/ln-setcov.ps.gz

<font color=red> Students' lessons:</font> 
   * [M11] http://www.sciencedirect.com/science/article/pii/S0020019010003777
   * [SS12] http://researcher.watson.ibm.com/researcher/files/us-rsaket/SetCover-confver.pdf
---
-->
<font color="cyan" size="+2">2. wireless fixed networks</font>

<font color="blue" size="+1">
2.1. The frequency assignment problem
i.e.
   a graph coloring problem</font>

%RED%
References:
%ENDCOLOR%
   * http://fap.zib.de/flavors/
   * [Aal15] section "Motivation": http://www.sciencedirect.com/science/article/pii/S0166218X13005647#
   * [CZ] pages 403-410 [[%ATTACHURL%/Lcolorings.pdf][download here]]
   * [GY92] pages 586-589, excluding th. 3.3 and subsect. 5 [[%ATTACHURL%/LcoloringsGY.pdf][download]]
   * http://www.vb-helper.com/tutorial_map_coloring.html <p> </p>

%RED% Students' lessons:%ENDCOLOR%
   * [BKTL04] http://comjnl.oxfordjournals.org/content/47/2/193.full.pdf+html
   * [Bal07] http://onlinelibrary.wiley.com/doi/10.1002/jgt.20228/epdf
   * [[%ATTACHURL%/distance1.pdf][&#91;AGK08]]] (network focused)
   * [Gal11] (network focused) https://ieeexplore.ieee.org/document/5970477
   * [Xal14] (vehicular network focused) http://link.springer.com/chapter/10.1007%2F978-3-319-07782-6_7 <p> </p>
%RED% For a thorough examination of the topic:%ENDCOLOR%
   * oriented L(2,1)-labeling
   * Backbone coloring http://www.springerlink.com/content/j7810m388j328760/<hr />
<font color="blue" size="+1">
 2.2. The minimum energy broadcast problem
i.e.
the minimum spanning tree problem</font>

%RED%
References:
%ENDCOLOR%
   * [J] pages 101-110 [[%ATTACHURL%/MinimalSpanningTrees.pdf][download here]]
   * [CLRS] [[%ATTACHURL%/MinSpanningTree.pdf][download here]]
   * [WCLF02] http://portal.acm.org/citation.cfm?id=603844
   * [Cal01] solo appendice http://www.springerlink.com/content/xgj5avpuela3twme/ <p> </p>

%RED% Students' lessons:%ENDCOLOR%
   * [Cal05] http://www.sciencedirect.com/science/article/pii/S1570870503000684
   * [M95] https://www.sciencedirect.com/science/article/pii/0166218X9400095U
   * [Gal07] https://link.springer.com/chapter/10.1007/978-3-540-75142-7_21
   * [N08] https://www.sciencedirect.com/science/article/abs/pii/S1570870507001254 <p> </p>

%RED% For a thorough examination of the topic:%ENDCOLOR%
   * Approximation bound of 6 by Ambüehl https://link.springer.com/chapter/10.1007/11523468_92
   * [FNP06] http://portal.acm.org/citation.cfm?id=1187436.1216587 <p> </p> <hr />
<font color="blue" size="+2">3. fixed sensor networks</font>

<font color="blue" size="+1">
 3.1. The data mule scheduling problem
i.e.
the traveling salesman problem</font>

%RED%
References:
%ENDCOLOR%
   * [J] pages 433-436,446-448 [[%ATTACHURL%/scan_calamo_2019-09-17-14-59-23.pdf][download here]] and [[%ATTACHURL%/scan_calamo_2019-09-17-15-00-33.pdf]][here]]
   * [SG07] Introduction http://mesl.ucsd.edu/sugiryo/papers/techreport07.pdf <p> </p>

%RED% Students' lessons:%ENDCOLOR%
   * [SG07] http://mesl.ucsd.edu/sugiryo/papers/techreport07.pdf
   * [Cal15] https://link.springer.com/chapter/10.1007/978-3-319-28472-9_5
   * [LES14] https://www.sciencedirect.com/science/article/abs/pii/S157087051400016X
   * [Mal19] http://www.optimization-online.org/DB_FILE/2017/02/5862.pdf <p> </p>

<font color="blue" size="+1">
3.2. The data Collection in ad-hoc networks
i.e.
   the connected Dominating Set Problem </font>

%RED%
References:
%ENDCOLOR%
   * [Sal19] https://ieeexplore.ieee.org/document/8813084
   * https://en.wikipedia.org/wiki/Connected_dominating_set
   * https://en.wikipedia.org/wiki/Dominating_set
   * [Ral04] https://citeseerx.ist.psu.edu/viewdoc/download?rep=rep1&type=pdf&doi=10.1.1.134.6269
   * [PS10] http://www.airccse.org/journal/graphhoc/papers/0910jgraph5.pdf <p> </p>

%RED% Students' lessons:%ENDCOLOR%
   * [LL23] https://www.worldscientific.com/doi/epdf/10.1142/S0129054123420029<hr />
<font color="orange" size="+2">4. mobile sensor networks</font>

<font color="blue" size="+1">
4.1. The centralized deployment of a mobile sensor network
i.e.
   the minimum cost perfect matching in bipartite graphs</font>

%RED%
References:
%ENDCOLOR%
   * [[%ATTACHURL%/DeploymentSurvey.pdf][CSS09]]: an interesting survey on the deployment - it contains an error: the Virtual Force Approach is considered as an example of centralized deployment, while it is a distributed approach
   * [WY06]: https://ieeexplore.ieee.org/document/1655671
   * [GYrosso] pages 1103-1111 [[%ATTACHURL%/Matching.pdf][download here]]
   * [CLRS] [[%ATTACHURL%/MaxMatchingBip.pdf][download here]]
   * notes by Paritosh Kavathekar: https://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/kavathekar-scribe.pdf
   * notes by Vempala: https://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/vempala-blossom.pdf (matching in the not bip. case)
   * notes by Modiano: https://ocw.mit.edu/courses/6-263j-data-communication-networks-fall-2002/resources/lectures17_18/ <p> </p>

%RED% Students' lessons:%ENDCOLOR%
   * [Fal10] [[%ATTACHURL%/Deployment.pdf][Carrier-based Deployment]]
   * [HZ14] http://www.csroc.org.tw/journal/JOC24-4/JOC24-4-4.pdf
   * [Dal10] https://ieeexplore.ieee.org/document/5695614 (Sweep Coverage)
   * [GM15] https://link.springer.com/chapter/10.1007/978-3-319-14974-5_26 (Sweep Coverage) <p> </p>

%RED% For a thorough examination of the topic:%ENDCOLOR%
   * notes by Michel X. Goemans: https://math.mit.edu/~goemans/18433S09/matching-notes.pdf
   * [Mal99] http://www.eecs.berkeley.edu/~ananth/1999-2001/Nick/NickPaper99.pdf<hr />

<font color="blue" size="+1">
4.2. Self-deployment of a mobile sensor network
i.e.
   the Voronoi Diagram</font>

%RED%
References:
%ENDCOLOR%
   * [HMS02] [[%ATTACHURL%/forze.pdf][virtual forces]]
   * http://www.ams.org/samplings/feature-column/fcarc-voronoi
   * http://en.wikipedia.org/wiki/Fortune%27s_algorithm
   * [Bal09] http://www.dsi.uniroma1.it/~calamo/PDF-FILES/VorLag.pdf
   * [YWD06] http://cs.pnw.edu/~yang246/papers/MASS06.pdf <p> </p>

%RED% Students' lessons:%ENDCOLOR%
   * [Dal18] https://www.actapress.com/Abstract.aspx?paperId=45861
   * [HV05] - note: eq. 1 is wrong: a "-" is missing right after cR https://ieeexplore.ieee.org/abstract/document/1369347
   * [L94] http://www.karlchenofhell.org/cppswp/lischinski.pdf
   * [NSM16] https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5038770/
   * [TJK08] https://ieeexplore.ieee.org/abstract/document/4770105
   * [Kal14] https://hal.inria.fr/hal-01095749/file/Survey.pdf <p> </p>

%RED% For a thorough examination of the topic:%ENDCOLOR%
   * [WCL06] G. Wang, G. Cao, and T. La Porta. Movement-assisted sensor deployment, IEEE Trans. on Mobile Computing, vol. 6, pp. 640-652, 2006.
   * http://research.engineering.wustl.edu/~pless/506/l16quack.html
   * http://research.engineering.wustl.edu/~pless/506/l17.html
   * https://www.youtube.com/watch?v=7eCrHAv6sYY
   * https://www.youtube.com/watch?v=Y5X1TvN9TpM
   * Delunay triangulation <p> </p> <p> </p>

<font color="blue" size="+1">
4.3. Monitoring by UAVs
i.e.
   what? </font>

%RED% Students' lessons:%ENDCOLOR%
   * [GDW12] http://ieeexplore.ieee.org/document/6214705/
   * [CB05] http://www.sciencedirect.com/science/article/pii/S0895717705001639
   * [Yal20]https://ieeexplore.ieee.org/document/9108245<hr /> <p> </p>

</td> <td style="border-left: 1px solid gray; padding-left: 5px;" width="50%">
---+++ <font color="blue" size="+2"> Italiano</font>
---
Si riportano qui gli argomenti orientativi che si intende affrontare durante il corso ed i riferimenti per studiare.
Per un maggior dettaglio sugli argomenti effettivamente svolti si rimanda al diario delle lezioni.

*NOTA:* Gli articoli possono essere scaricati gratuitamente connettendosi alla rete Sapienza.
Per favore, fatemi sapere se doveste notare che qualche link non funziona.

---
<font color="green" size="+2">0. Introduzione al corso</font>

<font color="red" size="+2">1. reti cablate</font>

<font color="blue" size="+1">
1.1. Il problema dell'instradamento
ovvero
il problema della ricerca del cammino più corto di costo minimo (pesi pari al costo o alla probabilità di guasto della connessione)</font>

%RED%
Riferimenti per studiare:
%ENDCOLOR%
   * [J] cap.3, escluse sez. 3.2, 3.4, 3.10 [[%ATTACHURL%/ShortestPath.pdf][scarica qui]]
   * [CLRS] [[%ATTACHURL%/1_1_SingleSourceShortestPaths.pdf][scarica qui]]
   * [L] sez. 3.4 pagg. 511-521 + pagg. 440-442 + 451-456 [[%ATTACHURL%/Packet-Routing_Algorithms.pdf][scarica qui]] [[%ATTACHURL%/ButterflyBenes.pdf][...e qui]] <p> </p>

%RED% Tesine:%ENDCOLOR%
   * [Aal14] Analisi di politiche di packet forwarding per problemi di flusso massimo e medio in una rete particolare (line network). http://link.springer.com/chapter/10.1007%2F978-3-642-54423-1_53
   * [Lal16] Un algoritmo iterativo efficiente di tipo MapReduce per determinare le componenti connesse in grafi di grandi dimensioni https://ieeexplore.ieee.org/document/7515231
   * [NCO13] Definizione di weakly dynamic graphs, ed un algoritmo efficiente per calcolare in anticipo su di essi i cammini minimi per ogni possibile configurazione [[%ATTACHURL%/Routing.pdf][scarica qui]]
   * [W14] Algoritmi adattivi ed efficienti dal punto di vista energetico per costruire Multipath Routing in WSNs http://link.springer.com/chapter/10.1007%2F978-3-662-44917-2_32
<p> </p>
%RED% Possibili approfondimenti:%ENDCOLOR%
   * algoritmi di instradamento dinamici per topologie di interconnessione
   * [GR93] Un miglioramento euristico dell'algoritmo di Bellman-Ford algorithm progettato dal famoso Andrew V. Goldberg 
 https://www.sciencedirect.com/science/article/pii/089396599390022F
<hr />

<font color="blue" size="+1">
1.2. Il problema del layout di topologie di interconnessione
ovvero
il problema del disegno ortogonale su griglia
</font>

%RED%
Riferimenti per studiare:
%ENDCOLOR%
   * [L80] solo prima pagina [[%ATTACHURL%/HtreeLeiserson_p1.pdf][scarica qui]]
   * [W81] solo disegno e osservazioni su di esso [[%ATTACHURL%/Compact_Layouts_of_Banyan-FFT_Networks.pdf][scarica qui]]
   * [EE00] tutto esclusa sez. 3.3. http://onlinelibrary.wiley.com/doi/10.1002/1097-0037%28200009%2936:2%3C91::AID-NET3%3E3.0.CO;2-4/abstract
   * [L] pagg. 392-396 [[%ATTACHURL%/HyperCube.pdf][scarica qui]]
   * [YVP99] tutto [[%ATTACHURL%/YVP99.pdf][scarica qui]]
   * [YP97] sezioni 1 e 2 [[%ATTACHURL%/LayoutCompleto.pdf][scarica qui]] <p> </p>
%RED% Tesine:%ENDCOLOR%
   * [GG01] Analisi del layout degli ipercubi http://arxiv.org/abs/cs/0105034v1
   * [L80] Il determinante lavoro di Leiserson sul layout degli alberi binari completi [[%ATTACHURL%/HtreeLeiserson.pdf][scarica qui]]
   * [Mal13] reti 3D che usano un protocollo di comunicazione multicast efficiente https://ieeexplore.ieee.org/document/6498567
   * [Xal09] A low-radix and low-diameter 3D interconnection network design https://ieeexplore.ieee.org/document/4798234
 <p> </p>

%RED% Possibili approfondimenti:%ENDCOLOR%
   * Il lavoro iniziale di Leighton e Rosenberg: http://www.dtic.mil/dtic/tr/fulltext/u2/a143430.pdf
   * Il lavoro con il layout a 45° della Butterfly: https://www.researchgate.net/publication/220246076_A_Compact_Layout_of_the_Butterfly
 <p> </p> <hr />

<font color="blue" size="+1">
1.3. Il problema di infettare (e difendere) una rete con un worm
ovvero
   il problema della minima copertura di vertici
</font>

%RED%
Riferimenti per studiare:
%ENDCOLOR%
   * http://it.wikipedia.org/wiki/Worm
   * http://expertvoices.nsdl.org/cornell-info204/2009/03/12/graph-theory-applications-optimizing-worm-propagation-in-networks/
   * http://en.wikipedia.org/wiki/Vertex_cover
   * http://en.wikipedia.org/wiki/K%C3%B6nig%27s_theorem_%28graph_theory%29
   * [CLRS] [[%ATTACHURL%/1_3_VertexCover.pdf][scarica qui]]
   * [GYnero] [[%ATTACHURL%/document.pdf][scarica qui]] 
   * [CA23] https://ieeexplore.ieee.org/document/10296816
<p> </p>
%RED% Tesine:%ENDCOLOR%
   * [Aal18] https://cs.emis.de/LIPIcs/volltexte/2018/9152/pdf/LIPIcs-ICALP-2018-148_.pdf
   * [Cal14] http://link.springer.com/chapter/10.1007/978-3-662-44602-7_2
   * [Fal07] [[%ATTACHURL%/Combinatorial-Optimisation-of-Worm-Propagationon-an-Unknown-Network.pdf][Combinatorial Optimisation of Worm Propagationon an Unknown Network]]
   * [KM09] https://ajc.maths.uq.edu.au/pdf/45/ajc_v45_p235.pdf (eternal VC)
   * [KM16] https://www.researchgate.net/publication/264123208_Protecting_a_Graph_with_Mobile_Guards (approfondire solo la parte di eternal VC)<hr />
<!--
<font color=blue size="+1"> 
1.4. Il problema di minimizzare un circuito booleano
ovvero 
   il problema della minima copertura di insiemi
</font>

<font color=red>
Riferimenti per studiare:
</font>
   * [CLRS] [[%ATTACHURL%/MinSetCover.pdf][scarica qui]]
   * http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK5/NODE201.HTM
   * http://en.wikipedia.org/wiki/Set_cover_problem
   * Notes of Prof. J. Cherian, Univ. of Waterloo - Canada. http://www.math.uwaterloo.ca/~jcheriya/PS_files/ln-setcov.ps.gz

<font color=red> Tesine:</font> 
   * [M11] http://www.sciencedirect.com/science/article/pii/S0020019010003777
   * [SS12] http://researcher.watson.ibm.com/researcher/files/us-rsaket/SetCover-confver.pdf
---
-->
<font color="cyan" size="+2">2. reti wireless fisse </font>

<font color="blue" size="+1">
 2.1. Il problema dell'assegnazione di frequenze
ovvero
   un problema di colorazione di grafi
</font>

%RED%
Riferimenti per studiare:
%ENDCOLOR%
   * http://fap.zib.de/flavors/
   * [Aal15] sez. "Motivation": http://www.sciencedirect.com/science/article/pii/S0166218X13005647#
   * [CZ] pagg. 403-410/pages 403-410 [[%ATTACHURL%/Lcolorings.pdf][scarica qui]]
   * [GY92] pagg. 586-589, escluso th. 3.3 e par. 5/pages 586-589, excluding th. 3.3 and subsect. 5 [[%ATTACHURL%/LcoloringsGY.pdf][scarica qui]]
   * http://www.vb-helper.com/tutorial_map_coloring.html <p> </p>
%RED% Tesine:%ENDCOLOR%
   * [BKTL04] http://comjnl.oxfordjournals.org/content/47/2/193.full.pdf+html
   * [Bal07] http://onlinelibrary.wiley.com/doi/10.1002/jgt.20228/epdf
   * [[%ATTACHURL%/distance1.pdf][&#91;AGK08]]] (più rivolto alle reti)
   * [Gal11] (anche questo rivolto alle reti) https://ieeexplore.ieee.org/document/5970477
   * [Xal14] (reti veicolari) http://link.springer.com/chapter/10.1007%2F978-3-319-07782-6_7 <p> </p>
%RED% Possibili approfondimenti:%ENDCOLOR%
   * L(2,1)-etichettatura orientata
   * Backbone coloring http://www.springerlink.com/content/j7810m388j328760/<hr />
<font color="blue" size="+1">
 2.2. Il problema del broadcast con minimo dispendio di energia
ovvero
il problema del minimo albero ricoprente
</font>

%RED%
Riferimenti per studiare:
%ENDCOLOR%
   * [J] pagg. 101-110/pages 101-110 [[%ATTACHURL%/MinimalSpanningTrees.pdf][scarica qui]]
   * [CLRS] [[%ATTACHURL%/MinSpanningTree.pdf][scarica qui]]
   * [WCLF02] http://portal.acm.org/citation.cfm?id=603844
   * [Cal01] solo appendice http://www.springerlink.com/content/xgj5avpuela3twme/ <p> </p>
%RED% Tesine:%ENDCOLOR%
   * [Cal05] http://www.sciencedirect.com/science/article/pii/S1570870503000684
   * [M95] https://www.sciencedirect.com/science/article/pii/0166218X9400095U
   * [Gal07] https://link.springer.com/chapter/10.1007/978-3-540-75142-7_21
   * [N08] https://www.sciencedirect.com/science/article/abs/pii/S1570870507001254 <p> </p>
%RED% Possibili approfondimenti:%ENDCOLOR%
   * Bound di approssimazione di 6 di Ambüehl https://link.springer.com/chapter/10.1007/11523468_92
   * [FNP06] http://portal.acm.org/citation.cfm?id=1187436.1216587<hr />
<font color="blue" size="+2">3. reti di sensori fisse </font>
<font color="blue" size="+1">
 3.1. Il problema del data mule
ovvero
il problema del commesso viaggiatore
</font>

%RED%
Riferimenti per studiare:
%ENDCOLOR%
   * [J] pages 433-436,446-448 [[%ATTACHURL%/scan_calamo_2019-09-17-14-59-23.pdf][scarica qui]] e [[%ATTACHURL%/scan_calamo_2019-09-17-15-00-33.pdf]][qui]] <p> </p>
   * [SG07] Introduction http://mesl.ucsd.edu/sugiryo/papers/techreport07.pdf
%RED% Tesine:%ENDCOLOR%
   * [SG07] http://mesl.ucsd.edu/sugiryo/papers/techreport07.pdf
   * [Cal15] https://link.springer.com/chapter/10.1007/978-3-319-28472-9_5
   * [LES14] https://www.sciencedirect.com/science/article/abs/pii/S157087051400016X
   * [Mal19] http://www.optimization-online.org/DB_FILE/2017/02/5862.pdf <p> </p>
<font color="blue" size="+1">
3.2. Il Data Collection in reti di sensori
ovvero
   il problema dell'insieme dominante connesso </font>

%RED%
Riferimenti per studiare:
%ENDCOLOR%
   * [Sal19] https://ieeexplore.ieee.org/document/8813084
   * https://en.wikipedia.org/wiki/Connected_dominating_set
   * https://en.wikipedia.org/wiki/Dominating_set
   * [Ral04] https://citeseerx.ist.psu.edu/viewdoc/download?rep=rep1&type=pdf&doi=10.1.1.134.6269
   * [PS10] http://www.airccse.org/journal/graphhoc/papers/0910jgraph5.pdf <p> </p>
%RED% Tesine:%ENDCOLOR%
   * [LL23] https://www.worldscientific.com/doi/epdf/10.1142/S0129054123420029<hr />
<font color="orange" size="+2">4. reti di sensori mobili</font>

<font color="blue" size="+1">
4.1. Il problema del dispiegamento centralizzato di sensori mobili
ovvero
   il problema dell'accoppiamento perfetto di costo minimo su grafo bipartito
</font>

%RED%
Riferimenti per studiare:
%ENDCOLOR%
   * [[%ATTACHURL%/DeploymentSurvey.pdf][CSS09]]: una rassegna interessante sul dispiegamento - contiene un errore: l'approccio basato sulle forze virtuali viene considerato un esempio di protocollo centralizzato mentre è distribuito
   * [WY06]: https://ieeexplore.ieee.org/document/1655671
   * [GYrosso] pagg. 1103-1111 [[%ATTACHURL%/Matching.pdf][scarica qui]]
   * [CLRS] [[%ATTACHURL%/MaxMatchingBip.pdf][scarica qui]]
   * note di Paritosh Kavathekar: https://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/kavathekar-scribe.pdf
   * note di Vempala: https://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/vempala-blossom.pdf (matching non bip.)
   * note di Modiano: https://ocw.mit.edu/courses/6-263j-data-communication-networks-fall-2002/resources/lectures17_18/ <p> </p>
%RED% Tesine:%ENDCOLOR%
   * [Fal10] [[%ATTACHURL%/Deployment.pdf][Carrier-based Deployment]]
   * [HZ14] http://www.csroc.org.tw/journal/JOC24-4/JOC24-4-4.pdf
   * [Dal10] https://ieeexplore.ieee.org/document/5695614 (Sweep Coverage)
   * [GM15] https://link.springer.com/chapter/10.1007/978-3-319-14974-5_26 (Sweep Coverage) <p> </p>
%RED% Possibili approfondimenti:%ENDCOLOR%
   * note di Michel X. Goemans: https://math.mit.edu/~goemans/18433S09/matching-notes.pdf
   * [Mal99] http://www.eecs.berkeley.edu/~ananth/1999-2001/Nick/NickPaper99.pdf<hr />
<font color="blue" size="+1">
4.2. Il problema del dispiegamento distribuito di sensori mobili
ovvero
   il problema del diagramma di Voronoi
</font>

%RED%
Riferimenti per studiare:
%ENDCOLOR%
   * [HMS02] [[%ATTACHURL%/forze.pdf][virtual forces]]
   * http://www.ams.org/samplings/feature-column/fcarc-voronoi
   * http://en.wikipedia.org/wiki/Fortune%27s_algorithm
   * [Bal09] http://www.dsi.uniroma1.it/~calamo/PDF-FILES/VorLag.pdf
   * [YWD06] http://cs.pnw.edu/~yang246/papers/MASS06.pdf <p> </p>
%RED% Tesine:%ENDCOLOR%
   * [Dal18] https://www.actapress.com/Abstract.aspx?paperId=45861
   * [HV05] - nota: l'eq. 1 è sbagliata, manca un meno dopo cR https://ieeexplore.ieee.org/abstract/document/1369347
   * [L94] http://www.karlchenofhell.org/cppswp/lischinski.pdf
   * [NSM16] https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5038770/
   * [TJK08] https://ieeexplore.ieee.org/abstract/document/4770105
   * [Kal14] https://hal.inria.fr/hal-01095749/file/Survey.pdf <p> </p>
%RED% Possibili approfondimenti:%ENDCOLOR%
   * [WCL06] G. Wang, G. Cao, and T. La Porta. Movement-assisted sensor deployment, IEEE Trans. on Mobile Computing, vol. 6, pp. 640-652, 2006.
   * http://research.engineering.wustl.edu/~pless/506/l16quack.html
   * http://research.engineering.wustl.edu/~pless/506/l17.html
   * https://www.youtube.com/watch?v=7eCrHAv6sYY
   * https://www.youtube.com/watch?v=Y5X1TvN9TpM
   * la triangolazione di Delunay <p> </p> <p> </p>
<font color="blue" size="+1">
4.3. Monitorare tramite UAVs
ovvero
   TSP multiplo con vincoli (più o meno)
</font>

%RED% Tesine:%ENDCOLOR%
   * [GDW12] http://ieeexplore.ieee.org/document/6214705/
   * [CB05] http://www.sciencedirect.com/science/article/pii/S0895717705001639
   * [Yal20] https://ieeexplore.ieee.org/document/9108245<hr />
</td> </tr> </tbody> </table>

---+++ <font color="blue" size="+2"> Bibliografia/Bibliography</font>

<font color="red" size="+2">Libri/Books</font>

   * [CZ] G. Chartrand, P. Zhang, Chromatic Graph Theory, CRC Press 2009.
   * [CLRS] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms and Data Structures, Mc Graw-Hill 2001.
   * [GYnero] J.L. Gross, J. Yellen, Graph Theory and its applications, Chapman & Hall 2006.
   * [GYrosso] J.L. Gross, J. Yellen, Handbook of Graph Theory, CRC Press 2004
   * [J] D. Jungnickel, Graphs, Networks and Algorithms, Springer, 2005.
   * [L] F.T.Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, 1991.

<font color="red" size="+2">Articoli/Papers</font>

   * [Aal15] C. Archetti, N. Bianchessi, A. Hertz, A. Colombet, F. Gagnon, "Directed weighted improper coloring for cellular channel allocation", Discrete Applied Math. 182, 46-60, 2015.
   * [Bal09] N. Bartolini, T. Calamoneri, T. La Porta, A. Massini, S. Silvestri, " Autonomous deployment of heterogeneous mobile sensors ", Proc. of 17th IEEE Int.l Conference on Networks Protocols (ICNP '09)
   * [CA23] C. Candemir, V.K.Akram, "Application of Minimum Vertex Cover Problem in Functional Brain Connectivity Graphs", Proc. of Innovations in Intelligent Systems and Applications Conference (ASYU), pp. 1-5, 2023.
   * [CSS09] J. Chen, E. Shen, Y. Sun, "The Deployment Algorithms in Wireless Sensor Networks: a Survey", Information Technology Journal 8(3) 2009.
   * [Cal15] Gui Citovsky, Jie Gao Joseph S. B. Mitchell Jiemin Zeng. "Exact and Approximation Algorithms for Data Mule Scheduling in a Sensor Network", International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS), pp. 57-70, 2015.
   * [Cal01] A. Clementi, P. Crescenzi, P. Penna, G. Rossi and P. Vocca. On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs. 18th STACS'01, LNCS 2010, 2001.
   * [EE00] G. Even, S. Even: Embedding Interconnection Networks in Grids via the Layered Cross Product, Networks 36(2), pp. 91-95, 2000.
   * [GR93] A.V.Goldberg, T.Radzik. A Heuristic Improvement of the Bellman-Ford Algorithm. Appl. Math. Lett. 6(3), 3-6 (1993).
   * [GY92] J.R. Griggs, R.K. Yeh: Labelling graphs with a condition at distance 2. SIAM J. Disc. Math. 5(4), 586-595, 1992.
   * [HMS02] A. Howard, M.J. Mataric, G.S. Sukhatme: Mobile Sensor Network Deployment using Potential Fields: A Distributed, Scalable Solution to the Area Coverage Problem. 6th International Symposium on Distributed Autonomous Robotics Systems (DARS02), 2002.
   * [L80] C.E. Leiserson: Area Efficient Graph Layouts (for VLSI). Proc. IEEE FOCS 1980.
   * [Mal99] N. Mc Keown, A. Mekkittikul, V. Anantharam, J. Walrand: Achieving 100% throughput in an input queued switch. IEEE Trans. on Communications, 47(8), 1999.
   * [PS10] G.N. Purohit and U. Sharma: Constructing Minimum Connected Dominating Set: Algorithmic approach. International journal on applications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC) Vol. 2, No. 3, September 2010
   * [Ral04] L. Ruana, H. Dub, X. Jiab, W. Wuc, Y. Lid, K. Ko. A greedy approximation for minimum connected dominating sets. Theoretical Computer Science 329 (2004) 325 – 330.
   * [Sal19] W. Shi, W. Liu, T. Wang, Z. Zeng, G. Zhi: Adding Duty Cycle Only in Connected Dominating Sets for Energy Efficient and Fast Data Collection. IEEE Access, 7, 2019.
   * [SG07] R. Sugihara, R.K. Gupta: Data Mule Scheduling in Sensor Networks: Scheduling under Location and Time Constraints. UCSD CSE Technical Report CS2007-0911.
   * [WCL06] G. Wang, G. Cao, and T. La Porta. Movement-assisted sensor deployment, IEEE Trans. on Mobile Computing, vol. 6, pp. 640-652, 2006.
   * [WCLF02] P.-J. Wan, G. Calinescu, X.-Y. Li, O. Frieder. Minimum-Energy Broadcast Routing in Static Ad-hoc Wireless Networks. Wireless Networks 8(6), 607 8211; 617, 2002.
   * [W81] D.S. Wise: Compact Layouts of Banyan/FFT Networks, VLSI Systems and Computations, pp.186-195, 1981.
   * [WY06] J. Wu, S. Yang: Optimal Movement-Assisted Sensor Deployment and Its Extensions in Wireless Sensor Networks. Proceedings 12th International Conference on Parallel and Distributed Systems (ICPADS), 2006.
   * [YWD06] S. Yang, J. Wu, F. Dai. "Localized Movement-Assisted Sensor Deployment in Wireless Sensor Networks", MASS 2006.
   * [YP97] C.-H. Yeh, B. Parhami: VLSI Layouts of Complete graphs and star graphs. Information Processing Letters 68, pp. 39-45, 1998.
   * [YVP99] C.-H. Yeh, E.A. Varvarigos, and B. Parhami: Efficient VLSI layouts of hypercubic networks, Proc. Symp. Frontiers of Massively Parallel Computation, 1999, pp. 98- 105

<font color="red" size="+2">Articoli per tesine/Papers for lessons</font>

   * [Aal18] E. Akrida, G.B. Mertzios, P.G. Spirakis, V. Zamaraev, "Temporal Vertex Cover with a Sliding Time Window", Proc. of 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). LIPICS Article No. 148; pp. 148:1–148:14.
   * [Aal14] A. Antoniadis, N. Barcelo, D. Cole, K. Fox, B. Moseley, M. Nugent, K. Pruhs, Packet Forwarding Algorithms in a Line Network, Proc. LATIN 2014, LNCS 8392, pp. 610–621, 2014.
   * [AGK08] E. Aryafar, O. Gurewitz, E.W. Knightly, Distance-1 Constrained Channel Assignment in Single Radio Wireless Mesh Networks, IEEE INFOCOM 2008.
   * [BKTL04] H. L. Bodlaender, T. Kloks, R. B. Tan, J. van Leeuwen: Approximations for lambda-Colorings of Graphs. Comput. J. 47(2): 193-204 (2004)
   * [Bal07] H. Broersma, F. Fomin, P. Golovach, G. Woeginger, "Backbone coloring for graphs: tree and path backbones", J. of Graph Theory 55(2), 2007.
   * [Cal05] J. Cartigny, F. Ingelrest, D. Simplot-Ryl, I. Stojmenovic, Localized LMST and RNG based minimum-energy broadcast protocols in ad hoc networks, Ad Hoc Networks 3 (2005) 1–16
   * [Cal14] B. Caskurlu, V. Mkrtchyan, O. Parekh, K. Subramani, On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs, Proc. of TCS 2014, LNCS 8705, pp. 13–26, 2014
   * [CB05] Y. Chan, S.F. Baker. The Multiple Depot, Multiple Traveling Salesmen Facility-Location Problem: Vehicle Range, Service Frequency, and Heuristic Implementations. Mathematical and Computer Modelling 41 (2005) 1035-1053.
   * [Dal18] L. Deng, X. Ma, J. Gu, Y. Li "Detection and repair of coverage holes in mobile sensor networks using sub-Voronoi cells" International Journal of Robotics and Automation - 2018
   * [Dal10] J. Du, Y. Li, H. Liu, K. Sha, "On Sweep Coverage with Minimum Mobile Sensors", IEEE 16th International Conference on Parallel and Distributed Systems, pp. 283-290, 2010.
   * [Fal07] E. Filiol, E. Franc, A. Gubbioli, B. Moquet, G. Roblot, Combinatorial Optimisation of Worm Propagation on an Unknown Network. World Academy of Science, Engineering and Technology International Journal of Computer and Information Engineering Vol. 1, No. 10, 2007
   * [Fal10] G. Fletcher, X. Li, A. Nayak, I. Stojmenovic: Back-Tracking based Sensor Deployment by a Robot Team. Proceedings 7th IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON), 2010.
   * [FNP06] Flammini, Navarra, Perennes, The real approximation factor of the MST heuristic for the minimum energy broadcasting, Journal of Experimental Algorithmics (JEA) 11, 2006.
   * [Gal07] L. Gasieniec, E. Kantor, D.R. Kowalski, D. Peleg, C. Su, Energy and Time Efficient Broadcasting in Known Topology Radio Networks, Proc. DISC 2007, LNCS 4731, 2007.
   * [Gal11] L. Giarré, F.G. La Rosa, R. Pesenti, I. Tinnirello, Coloring-based Resource Allocations in Ad-hoc Wireless Networks, Proc. 10th IFIP Annual Mediterranean Ad Hoc Networking Workshop, 2011
   * [GDW12] N. Goddemeier, K. Daniel,C. Wietfeld. Role-Based Connectivity Management with Realistic Air-to-Ground Channels for Cooperative UAVs. IEEE J. on selected areas in communications, 30(5), 2012.
   * [GM15] B. Gorain and P.S. Mandal "Energy Efficient Sweep Coverage with Mobile and Static Sensors", Proc. CALDAM 2015, LNCS 8959, pp. 275–285, 2015.
   * [GG01] R. Greenberg, L. Guan. On the Area of Hypercube Layouts. Arxiv:cs/0105034. Inf. Process. Lett. 84(1): 41-46 (2002)
   * [HZ14] Zi-Qi Hao, Zhen-Jiang Zhang. "Two Centralized Energy-Efficient Deployment Algorithms for Mobile Nodes in a Mixed Wireless Sensor Network" Journal of Computers. 2014.
   * [HV05] N. Heo and P. K. Varshney, Energy-Efficient Deployment of Intelligent Mobile Sensor Networks, IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS 8212; PART A: SYSTEMS AND HUMANS, 35(1), 2005
   * [Kal14] I.Khoufi, P.Minet, A.Laouiti, S.Mahfoudh. "Survey of Deployment Algorithms in Wireless Sensor Networks: Coverage and Connectivity Issues and Challenges", International Journal of Autonomous and Adaptive Communications Systems (IJAACS), 2014
   * [KM09] W. Klostermeyer, C.M.Mynhardt. "Edge protection in graphs", AUSTRALASIAN JOURNAL OF COMBINATORICS 45, 235-250, 2009.
   * [KM16] W. Klostermeyer, C.M.Mynhardt. "Protecting a Graph with Mobile Guards", Applicable Analysis and Discrete Mathematics 10, 2016.
   * [L80] C.E. Leiserson: Area Efficient Graph Layouts (for VLSI). Proc. IEEE FOCS 1980.
   * [LEV14] L. Levin, A. Efrat, M. Segal: Collecting data in ad-hoc networks with reduced uncertainty. Ad Hoc Networks 17, 71-81, 2014.
   * [LL23] I.-C. Liao, H.-I. Lu: A Simple 2-Approximation for Maximum Leaf Spanning Tree. IJFCS 34(7), 795-805, 2023.
   * [L94] D. Lischinski. Incremental Delaunay Triangulation. In Graphics Gems IV, Paul. S. Heckbert, editor, Academic Press, 1994.
   * [Lal16] A. Lulli, E. Carlini, P. Dazzi, C. Lucchese, L. Ricci. Fast Connected Components Computation in Large Graphs by Vertex Pruning. IEEE Transactions on Parallel and Distributed Systems 28(3), 760-773, 2017. <!-- tenere -->
   * [M95] T. Matsui. The minimum spanning tree problem on a planar graph. Discr. Appl. Math. 58 91-94, 1995.
   * [Mal13] S.R. Moosavi, A.-M. Rahmani, P. Liljeberg, J. Plosila, H. Tenhunen. Enhancing Performance of 3D interconnection networks using an efficient multicast communication protocol. 1st Euromicro International Conference on Parallel, Distributed, and Network-Based Processing 2013.
   * [M11] H. Morizumi. Improved approximation algorithms for minimum AND-circuits problem via k-set cover. Information Processing Letters 111 218-221, 2011.
   * [Mal19] P.L.A. Munhoz, U. dos Santos Souza, P.H. Gonzales, L.S. Ochi, P. Michelon, L.M. de A. Drummond. "Locality sensitive heuristics for solving the Data Mule Routing Problem" ICAAM 2019.
   * [NCO13] M.NAKECHBANDI, J.-Y.COLIN, A.S.OULD CHEIKH. Routing and Rerouting in Weakly Dynamic Graphs. Proc. ECCS'13.
   * [NSM16] E. Niewiadomska-Szynkiewicz, A. Sikora, M. Marks. "A Movement-Assisted Deployment of Collaborating Autonomous Sensors for Indoor and Outdoor Environment Monitoring" Sensors, 2016.
   * [N08] A. Navarra. "3-Dimensional minimum energy broadcasting problem" Ad Hoc Networks 6, 734-743, 2008.
   * [SS12] R.Saket, M.Sviridenko. "New and Improved Bounds for the Minimum Set Cover Problem" APPROX 2012.
   * [TJK08] G.Tan, S.A.Jarvis, A.M.Kermarrec. "Connectivity-Guaranteed and Obstacle-Adaptive Deployment Schemes for Mobile Sensor Networks" ICDCS 2008.
   * [W14] S.Wan, Energy-Efficient and Adaptive Algorithms for Constructing Multipath Routing in Wireless Sensor Networks, Proc. NPC 2014, LNCS 8707, pp. 383–394, 2014.
   * [Xal14] J.Xu, W.Li, Z. Ma, S.Zhang, A New Channel Allocation Scheme for Vehicle Communication Networks, Proc. WASA 2014, LNCS 8491, pp. 66–77, 2014.
   * [Xal09] Y. Xu, Y. Du, B. Zhao, X. Zhou, Y. Zhang, J. Yang. A low-radix and low-diameter 3D interconnection network design. International Conference on Communication Software and Networks, 2009.
   * [Yal20] J.N. Yasin, S.A.S. Mohamed, M.-H. Haghbayan, Y. Heikkonen, H. Tenhunen, J. Plosila, Unmanned Aerial Vehicles (UAVs): Collision Avoidance Systems and Approaches. IEEE Access vol. 8, pp. 105139-105155, 2020.


<a href="WebHome1011" target="_self" title="Home">Home</a>
This topic: Algoreti > WebHome1011 > ProgrammaDelCorso
Topic revision: r85 - 2025-12-02 - TizianaCalamoneri