Network Algorithms

PROGRAM and TEXTBOOKS

The general topics to be covered 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.

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

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

[GDW12] http://ieeexplore.ieee.org/document/6214705/
[CB05] http://www.sciencedirect.com/science/article/pii/S0895717705001639
[Yal20]https://ieeexplore.ieee.org/document/9108245

Expansion of the Bibliographic Abbreviations

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.

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

Papers for students' 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.
[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.
[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.