nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Computing the Dynamic Diameter of Non-Deterministic Dynamic Networks is Hard

verfasst von : Emmanuel Godard, Dorian Mazauric

Erschienen in: Algorithms for Sensor Systems

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

A dynamic network is a communication network whose communication structure can evolve over time. The dynamic diameter is the counterpart of the classical static diameter, it is the maximum time needed for a node to causally influence any other node in the network. We consider the problem of computing the dynamic diameter of a given dynamic network. If the evolution is known a priori, that is if the network is deterministic, it is known it is quite easy to compute this dynamic diameter. If the evolution is not known a priori, that is if the network is non-deterministic, we show that the problem is hard to solve or approximate. In some cases, this hardness holds also when there is a static connected subgraph for the dynamic network.

In this note, we consider an important subfamily of non-deterministic dynamic networks: the time-homogeneous dynamic networks. We prove that it is hard to compute and approximate the value of the dynamic diameter for time-homogeneous dynamic networks.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Fast Rendezvous with Advice

Nächstes Kapitel Improved Spanners in Networks with Symmetric Directional Antennas

[AG13]

Afek, Y., Gafni, E.: Asynchrony from synchrony. In: Frey, D., Raynal, M., Sarkar, S., Shyamasundar, R.K., Sinha, P. (eds.) ICDCN 2013. LNCS, vol. 7730, pp. 225–239. Springer, Heidelberg (2013)CrossRef

[AKM14]

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, Heidelberg (2014)CrossRef

[BF03]

Bhadra, S., Ferreira, A.: Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In: Pierre, S., Barbeau, M., An, H.-C. (eds.) ADHOC-NOW 2003. LNCS, vol. 2865, pp. 259–270. Springer, Heidelberg (2003)CrossRef

[BXFJ03]

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

[CBS09]

Charron-Bost, B., Schiper, A.: The heard-of model: computing in distributed systems with benign faults. Distrib. Comput. 22(1), 49–71 (2009)CrossRefMATH

[CC06]

Chlebík, M., Chlebíková, J.: Complexity of approximating bounded variants of optimization problems. Theor. Comput. Sci. 354(3), 320–338 (2006)CrossRefMATH

[CFQS12]

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

[CG13]

Coulouma, É., Godard, E.: A characterization of dynamic networks where consensus is solvable. In: Moscibroda, T., Rescigno, A.A. (eds.) SIROCCO 2013. LNCS, vol. 8179, pp. 24–35. Springer, Heidelberg (2013)CrossRef

[CLN13]

Chalermsook, P., Laekhanukit, B., Nanongkai, D.: Independent set, induced matching, and pricing: connections and tight (subexponential time) approximation hardnesses. In: FOCS, pp. 370–379. IEEE Computer Society (2013)

[CLP11]

Chierichetti, F., Lattanzi, S., Panconesi, A.: Rumor spreading in social networks. Theor. Comput. Sci. 412(24), 2602–2610 (2011)CrossRefMathSciNetMATH

[Fer04]

Ferreira, A.: Building a reference combinatorial model for MANETs. IEEE Netw. 18(5), 24–29 (2004)CrossRef

[GP11]

Godard, E., Peters, J.: Consensus vs. broadcast in communication networks with arbitrary mobile omission faults. In: Kosowski, A., Yamashita, M. (eds.) SIROCCO 2011. LNCS, vol. 6796, pp. 29–41. Springer, Heidelberg (2011)CrossRef

[JLSW07]

Jones, E.P.C., Li, L., Schmidtke, J.K., Ward, P.A.S.: Practical routing in delay-tolerant networks. IEEE Trans. Mob. Comput. 6(8), 943–959 (2007)CrossRef

[KKW08]

Kossinets, G., Kleinberg, J., Watts, D.: The structure of information pathways in a social communication network. In: Proceedings of the 14th International Conference on Knowledge Discovery and Data Mining (KDD), pp. 435–443 (2008)

[KLO10]

Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: Proceedings of the 42nd ACM Symposium on Theory of computing (STOC), pp. 513–522. ACM (2010)

[LW09]

Liu, C., Wu, J.: Scalable routing in cyclic mobile networks. IEEE Trans. Parallel Distrib. Syst. 20(9), 1325–1338 (2009)CrossRef

[MS14]

Michail, O., Spirakis, P.G.: Traveling salesman problems in temporal graphs. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 553–564. Springer, Heidelberg (2014)CrossRef

[RR13]

Ros, F.J., Ruiz, P.M.: Minimum broadcasting structure for optimal data dissemination in vehicular networks. IEEE Trans. Veh. Technol. 62(8), 3964–3973 (2013)CrossRef

[RS13]

Raynal, M., Stainer, J.: Synchrony weakened by message adversaries vs asynchrony restricted by failure detectors. In: Fatourou, P., Taubenfeld, G. (eds.) PODC, pp. 166–175. ACM (2013)

[SV82]

Stockmeyer, L., Vazirani, V.: NP-completeness of some generalizations of the maximum matching problem. Inf. Process. Lett. 15(1), 14–19 (1982)CrossRefMathSciNetMATH

[Zha06]

Zhang, Z.: Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: overview and challenges. IEEE Commun. Surv. Tutor. 8(1), 24–37 (2006)CrossRef

Titel: Computing the Dynamic Diameter of Non-Deterministic Dynamic Networks is Hard
verfasst von: Emmanuel Godard
Dorian Mazauric
Verlag: Springer Berlin Heidelberg
Buch: Algorithms for Sensor Systems
Print ISBN: 978-3-662-46017-7

Electronic ISBN: 978-3-662-46018-4

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-662-46018-4_6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"