ProgrammaDelCorso < Algoreti

Program and Textbooks/ Programma del corso e Testi

English

Here, the general topics that will be dealt with during the course are listed. For a deeper detail, please go to the Lesson Diary.

NOTE: Papers can be freely downloaded by connecting to the Sapienza network.

0. Introduction to the Course

1. cable networks

1.1. The Routing problem i.e. the minimum cost shortest path

References:

[J] chap.3, excluding sect. 3.2, 3.4, 3.10 download here
[CLRS] download here
[L] sect. 3.4 pages 511-521 + pages 440-442 + 451-456 download here ...and here

Students' lessons:

[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 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
[WLC16] A survey of routing algorithm for mesh Network-on-Chip https://link.springer.com/article/10.1007/s11704-016-5431-8

For a thorough examination of the topic:

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

1.2. The layout of interconnection networks i.e. the orthogonal grid graph drawing

References:

[L80] only first page download here
[W81] only figures and related observations, 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 download here
[YVP99] whole download here
[YP97] sections 1 and 2 download here

Students' lessons:

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

For a thorough examination of the topic:

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

1.3. The problem of infecting a network with a worm i.e. the minimum vertex cover problem

References:

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 download here
[GYnero] download here
[CA23] https://ieeexplore.ieee.org/document/10296816

Students' lessons:

[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] 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)

2. wireless fixed networks

2.1. The frequency assignment problem i.e. a graph coloring problem

References:

http://fap.zib.de/flavors/
[Aal15] section "Motivation": http://www.sciencedirect.com/science/article/pii/S0166218X13005647#
[CZ] pages 403-410 download here
[GY92] pages 586-589, excluding th. 3.3 and subsect. 5 download
http://www.vb-helper.com/tutorial_map_coloring.html

Students' lessons:

[BKTL04] http://comjnl.oxfordjournals.org/content/47/2/193.full.pdf+html
[Bal07] http://onlinelibrary.wiley.com/doi/10.1002/jgt.20228/epdf
[AGK08] (network focused)
[CP04]://www.users.di.uniroma1.it/~calamo/PDF-FILES/coloring.pdf
[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

For a thorough examination of the topic:

oriented L(2,1)-labeling
Backbone coloring http://www.springerlink.com/content/j7810m388j328760/

2.2. The minimum energy broadcast problem i.e. the minimum spanning tree problem

References:

[J] pages 101-110 download here
[CLRS] download here
[WCLF02] http://portal.acm.org/citation.cfm?id=603844
[Cal01] solo appendice http://www.springerlink.com/content/xgj5avpuela3twme/

Students' lessons:

For a thorough examination of the topic:

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

3. fixed sensor networks

3.1. The data mule scheduling problem i.e. the traveling salesman problem

References:

[J] pages 433-436,446-448 download here and https://twiki.di.uniroma1.it/pub/Algoreti/ProgrammaDelCorso/scan_calamo_2019-09-17-15-00-33.pdf[here]]
[SG07] Introduction http://mesl.ucsd.edu/sugiryo/papers/techreport07.pdf

Students' lessons:

3.2. The data Collection in ad-hoc networks i.e. the connected Dominating Set Problem

References:

Students' lessons:

[LL23] https://www.worldscientific.com/doi/epdf/10.1142/S0129054123420029

4. mobile sensor networks

4.1. The centralized deployment of a mobile sensor network i.e. the minimum cost perfect matching in bipartite graphs

References:

CSS09: an interesting survey on the deployment with an error, i.e. 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 download here
[CLRS] 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/

Students' lessons:

[Fal10] 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)

For a thorough examination of the topic:

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

4.2. Self-deployment of a mobile sensor network i.e. the Voronoi Diagram

References:

Students' lessons:

[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

For a thorough examination of the topic:

[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

4.3. Monitoring by UAVs i.e. what?

Students' lessons:

Italiano

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.

0. Introduzione al corso

1. reti cablate

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)

Riferimenti per studiare:

[J] cap.3, escluse sez. 3.2, 3.4, 3.10 scarica qui
[CLRS] scarica qui
[L] sez. 3.4 pagg. 511-521 + pagg. 440-442 + 451-456 scarica qui ...e qui

Tesine:

[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 MapReduceper 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 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
[WLC16] Una carrellata di algoritmi di instradamento per mesh Network-on-Chip https://link.springer.com/article/10.1007/s11704-016-5431-8

Possibili approfondimenti:

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

1.2. Il problema del layout di topologie di interconnessione ovvero il problema del disegno ortogonale su griglia

Riferimenti per studiare:

[L80] solo prima pagina scarica qui
[W81] solo disegno e osservazioni su di esso 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 scarica qui
[YVP99] tutto scarica qui
[YP97] sezioni 1 e 2 scarica qui

Tesine:

[GG01] Analisi del layout degli ipercubi http://arxiv.org/abs/cs/0105034v1
[L80] Il determinante lavoro di Leiserson sul layout degli alberi binari completi 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

Possibili approfondimenti:

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

1.3. Il problema di infettare (e difendere) una rete con un worm ovvero il problema della minima copertura di vertici

Riferimenti per studiare:

Tesine:

[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] 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)

2. reti wireless fisse

2.1. Il problema dell'assegnazione di frequenze ovvero un problema di colorazione di grafi

Riferimenti per studiare:

http://fap.zib.de/flavors/
[Aal15] sez. "Motivation": http://www.sciencedirect.com/science/article/pii/S0166218X13005647#
[CZ] pagg. 403-410/pages 403-410 scarica qui
[GY92] pagg. 586-589, escluso th. 3.3 e par. 5/pages 586-589, excluding th. 3.3 and subsect. 5 scarica qui
http://www.vb-helper.com/tutorial_map_coloring.html

Tesine:

[BKTL04] http://comjnl.oxfordjournals.org/content/47/2/193.full.pdf+html
[Bal07] http://onlinelibrary.wiley.com/doi/10.1002/jgt.20228/epdf
[AGK08] (più rivolto alle reti)
[CP04]: http://wwwusers.di.uniroma1.it/~calamo/PDF-FILES/coloring.pdf
[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

Possibili approfondimenti:

L(2,1)-etichettatura orientata
Backbone coloring http://www.springerlink.com/content/j7810m388j328760/

2.2. Il problema del broadcast con minimo dispendio di energia ovvero il problema del minimo albero ricoprente

Riferimenti per studiare:

[J] pagg. 101-110/pages 101-110 scarica qui
[CLRS] scarica qui
[WCLF02] http://portal.acm.org/citation.cfm?id=603844
[Cal01] solo appendice http://www.springerlink.com/content/xgj5avpuela3twme/

Tesine:

Possibili approfondimenti:

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

3. reti di sensori fisse 3.1. Il problema del data mule ovvero il problema del commesso viaggiatore

Riferimenti per studiare:

[J] pages 433-436,446-448 scarica qui e https://twiki.di.uniroma1.it/pub/Algoreti/ProgrammaDelCorso/scan_calamo_2019-09-17-15-00-33.pdf[qui]]
[SG07] Introduction http://mesl.ucsd.edu/sugiryo/papers/techreport07.pdf

Tesine:

3.2. Il Data Collection in reti di sensori ovvero il problema dell'insieme dominante connesso

Riferimenti per studiare:

Tesine:

[LL23] https://www.worldscientific.com/doi/epdf/10.1142/S0129054123420029

4. reti di sensori mobili

4.1. Il problema del dispiegamento centralizzato di sensori mobili ovvero il problema dell'accoppiamento perfetto di costo minimo su grafo bipartito

Riferimenti per studiare:

CSS09: una rassegna interessante sul dispiegamente con un errore, cioè 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 scarica qui
[CLRS] 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/

Tesine:

[Fal10] 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)

Possibili approfondimenti:

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

4.2. Il problema del dispiegamento distribuito di sensori mobili ovvero il problema del diagramma di Voronoi

Riferimenti per studiare:

Tesine:

[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

Possibili approfondimenti:

[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

4.3. Monitorare tramite UAVs ovvero TSP multiplo con vincoli (più o meno)

Tesine:

Bibliografia/Bibliography

Libri/Books

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

Articoli/Papers

[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. Agreedyapproximationforminimumconnected 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

Articoli per tesine/Papers for lessons

[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.
[CP04] T. Calamoneri, R. Petreschi, "L(h,1)-Labeling Subclasses of Planar Graphs", Journal on Parallel and Distributed Computing, 64(3), pp. 414-426, 2004.
[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 JOURNAL 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.
[ML18] A.Majeed and S.Lee. "A Fast Global Flight Path Planning Algorithm Based on Space Circumscription and Sparse Visibility Graph for Unmanned Aerial Vehicle". Electronics 7(12)2018.
[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.
[WLC16] Y. Wu, C. Lu, Y. Chen "A survey of routing algorithm for mesh Network-on-Chip", Front. Comput. Sci., 10(4): 591–601, 2016.
[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.