Top

Published in:

2017 | OriginalPaper | Chapter

A Generic Framework for Computing Parameters of Sequence-Based Dynamic Graphs

Authors : Arnaud Casteigts, Ralf Klasing, Yessin M. Neggaz, Joseph G. Peters

Published in: Structural Information and Communication Complexity

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We presented in [12] an algorithm for computing a parameter called T -interval connectivity of dynamic graphs which are given as a sequence of static graphs. This algorithm operates at a high level, manipulating the graphs in the sequence as atomic elements with two types of operations: a composition operation and a test operation. The algorithm is optimal in the sense that it uses only \(O(\delta )\) composition and test operations, where \(\delta \) is the length of the sequence. In this paper, we generalize this framework to use various composition and test operations, which allows us to compute other parameters using the same high-level strategy that we used for T-interval connectivity. We illustrate the framework through the study of three minimization problems which refer to various properties of dynamic graphs, namely Bounded-Realization-of-the-Footprint, Temporal-Connectivity, and Round-Trip-Temporal-Diameter.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Effective Edge-Fault-Tolerant Single-Source Spanners via Best (or Good) Swap Edges

next chapter Gathering in Dynamic Rings

Aaron, E., Krizanc, D., Meyerson, E.: DMVP: foremost waypoint coverage of time-varying graphs. In: Kratsch, D., Todinca, I. (eds.) WG 2014. LNCS, vol. 8747, pp. 29–41. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-12340-0_3

Awerbuch, B., Even, S.: Efficient and reliable broadcast is achievable in an eventually connected network. In: Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 278–281. ACM (1984)

Barjon, M., Casteigts, A., Chaumette, S., Johnen, C., Neggaz, Y.M.: Testing temporal connectivity in sparse dynamic graphs. CoRR abs/1404.7634 (2014). (A French version appeared in Proceedings of ALGOTEL 2014)

Bournat, M., Datta, A.K., Dubois, S.: Self-stabilizing robots in highly dynamic environments. In: Bonakdarpour, B., Petit, F. (eds.) SSS 2016. LNCS, vol. 10083, pp. 54–69. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-49259-9_5 CrossRef

Bramas, Q., Tixeuil, S.: The complexity of data aggregation in static and dynamic wireless sensor networks. Inf. Comput. 255, 369–383 (2017)MathSciNetCrossRefMATH

Braud-Santoni, N., Dubois, S., Kaaouachi, M.H., Petit, F.: The next 700 impossibility results in time-varying graphs. Int. J. Netw. Comput. 6(1), 27–41 (2016)CrossRef

Bui-Xuan, B., Ferreira, A., Jarry, A.: Computing shortest, fastest, and foremost journeys in dynamic networks. Int. J. of Found. Comput. Sci. 14(2), 267–285 (2003)MathSciNetCrossRefMATH

Casteigts, A., Chaumette, S., Ferreira, A.: Characterizing topological assumptions of distributed algorithms in dynamic networks. In: Kutten, S., Žerovnik, J. (eds.) SIROCCO 2009. LNCS, vol. 5869, pp. 126–140. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11476-2_11. Full version in CoRR, abs/1102.5529CrossRef

Casteigts, A., Flocchini, P., Mans, B., Santoro, N.: Measuring temporal lags in delay-tolerant networks. IEEE Trans. Comput. 63(2), 397–410 (2014)MathSciNetCrossRefMATH

10.

Casteigts, A., Flocchini, P., Mans, B., Santoro, N.: Shortest, fastest, and foremost broadcast in dynamic networks. Int. J. Found. Comput. Sci. 26(4), 499–522 (2015)MathSciNetCrossRefMATH

11.

Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel, Emergent Distrib. Syst. 27(5), 387–408 (2012)CrossRef

12.

Casteigts, A., Klasing, R., Neggaz, Y.M., Peters, J.G.: Efficiently testing \(T\)-interval connectivity in dynamic graphs. In: Paschos, V.T., Widmayer, P. (eds.) CIAC 2015. LNCS, vol. 9079, pp. 89–100. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-18173-8_6 CrossRef

13.

Casteigts, A., Klasing, R., Neggaz, Y.M., Peters, J.G.: Calcul de Paramètres Minimaux dans les Graphes Dynamiques. In: 19èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (ALGOTEL) (2017)

14.

Dubois, S., Kaaouachi, M.-H., Petit, F.: Enabling minimal dominating set in highly dynamic distributed systems. In: Pelc, A., Schwarzmann, A.A. (eds.) SSS 2015. LNCS, vol. 9212, pp. 51–66. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21741-3_4 CrossRef

15.

Flocchini, P., Mans, B., Santoro, N.: On the exploration of time-varying networks. Theor. Comput. Sci. 469, 53–68 (2013)MathSciNetCrossRefMATH

16.

Gibbons, A., Rytter, W.: Efficient Parallel Algorithms. Cambridge University Press, Cambridge (1988)MATH

17.

Godard, E., Mazauric, D.: Computing the dynamic diameter of non-deterministic dynamic networks is hard. In: Gao, J., Efrat, A., Fekete, S.P., Zhang, Y. (eds.) ALGOSENSORS 2014. LNCS, vol. 8847, pp. 88–102. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46018-4_6

18.

Jain, S., Fall, K., Patra, R.: Routing in a delay tolerant network. In: Proceedings of SIGCOMM, pp. 145–158 (2004)

19.

JáJá, J.: An Introduction to Parallel Algorithms. Addison-Wesley, Boston (1992)MATH

20.

Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: Proceedings of STOC, pp. 513–522. ACM (2010)

21.

O’Dell, R., Wattenhofer, R.: Information dissemination in highly dynamic graphs. In: Proceedings of DIALM-POMC, pp. 104–110. ACM (2005)

22.

Raynal, M., Stainer, J., Cao, J., Wu, W.: A simple broadcast algorithm for recurrent dynamic systems. In: 2014 IEEE 28th International Conference on Advanced Information Networking and Applications (AINA), pp. 933–939. IEEE (2014)

23.

Viard, T., Latapy, M., Magnien, C.: Computing maximal cliques in link streams. Theor. Comput. Sci. 609, 245–252 (2016)MathSciNetCrossRefMATH

24.

Whitbeck, J., Dias de Amorim, M., Conan, V., Guillaume, J.L.: Temporal reachability graphs. In: Proceedings of MOBICOM, pp. 377–388. ACM (2012)

Title: A Generic Framework for Computing Parameters of Sequence-Based Dynamic Graphs
Authors: Arnaud Casteigts
Ralf Klasing
Yessin M. Neggaz
Joseph G. Peters
Publisher: Springer International Publishing
Book: Structural Information and Communication Complexity
Print ISBN: 978-3-319-72049-4

Electronic ISBN: 978-3-319-72050-0

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-72050-0_19

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner