nach oben

vorheriges Kapitel Advances in the Parallelization of the Simplex ...

nächstes Kapitel Random Surfing Without Teleportation

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

2015 | OriginalPaper | Buchkapitel

An Introduction to Temporal Graphs: An Algorithmic Perspective

Erstes Kapitel lesen

Autor: Othon Michail

Verlag: Springer International Publishing

Erschienen in: Algorithms, Probability, Networks, and Games

» Jetzt Zugang zum Volltext erhalten

Abstract

A temporal graph is, informally speaking, a graph that changes with time. When time is discrete and only the relationships between the participating entities may change and not the entities themselves, a temporal graph may be viewed as a sequence \(G_1,G_2\ldots ,G_l\) of static graphs over the same (static) set of nodes V. Though static graphs have been extensively studied, for their temporal generalization we are still far from having a concrete set of structural and algorithmic principles. Recent research shows that many graph properties and problems become radically different and usually substantially more difficult when an extra time dimension in added to them. Moreover, there is already a rich and rapidly growing set of modern systems and applications that can be naturally modeled and studied via temporal graphs. This, further motivates the need for the development of a temporal extension of graph theory. We survey here recent results on temporal graphs and temporal graph problems that have appeared in the Computer Science community.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Jetzt einloggen Kostenlos registrieren

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Jetzt informieren

In this article, we use “static” to refer to classical graphs. This is plausible as the opposite of “dynamic” that is also commonly used for temporal graphs. In any case, the terminology is still very far from being standard.

The sink is usually denoted by t in the literature. We use z instead as we reserve t to refer to time moments.

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)

Akrida, E.C., Gasieniec, L., Mertzios, G.B., Spirakis, P.G.: Ephemeral networks with random availability of links: Diameter and connectivity. In: Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures (SPAA), pp. 267–276. ACM (2014)

Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18, 235–253 (2006) CrossRefMATH

Asadpour, A., Goemans, M.X., Madry, A., Gharan, S.O., Saberi, A.: An \(O(\log n/ \log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 379–389. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2010). http://dl.acm.org/citation.cfm?id=1873601.1873633

Augustine, J., Pandurangan, G., Robinson, P., Upfal, E.: Towards robust and efficient computation in dynamic peer-to-peer networks. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 551–569. SIAM (2012)

Avin, C., Koucký, M., Lotker, Z.: How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 121–132. Springer, Heidelberg (2008) CrossRef

Bach, E., Shallit, J.: Algorithmic Number Theory. Efficient algorithms, vol. 1. MIT press, Cambridge (1996) MATH

Baker, B., Shostak, R.: Gossips and telephones. Discrete Math. 2(3), 191–193 (1972) MathSciNetCrossRefMATH

Berman, K.A.: Vulnerability of scheduled networks and a generalization of Menger’s theorem. Networks 28(3), 125–134 (1996) MathSciNetCrossRefMATH

10.

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

11.

Bläser, M.: A 3/4-approximation algorithm for maximum ATSP with weights zero and one. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004 and APPROX 2004. LNCS, vol. 3122, pp. 61–71. Springer, Heidelberg (2004) CrossRef

12.

Bollobás, B.: Modern Graph Theory. Graduate Texts in Mathematics. Springer, Heidelberg (1998). (Corrected edition, July 1, 1998) CrossRefMATH

13.

Bollobás, B.: Random Graphs. Cambridge Studies in Advanced Mathematics, 2nd edn. Cambridge University Press, Cambridge (2001) CrossRefMATH

14.

Broersma, H., Li, X.: Spanning trees with many or few colors in edge-colored graphs. Discuss. Math. Graph Theory 17(2), 259–269 (1997) MathSciNetCrossRefMATH

15.

Broersma, H., Li, X., Woeginger, G., Zhang, S.: Paths and cycles in colored graphs. Australas. J. Comb. 31, 299–311 (2005) MathSciNetMATH

16.

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

17.

Clementi, A.E., Macci, C., Monti, A., Pasquale, F., Silvestri, R.: Flooding time in edge-markovian dynamic graphs. In: Proceedings of the 27th ACM Symposium on Principles of Distributed Computing (PODC), pp. 213–222 (2008). http://doi.acm.org/10.1145/1400751.1400781

18.

Clementi, A.E., Pasquale, F., Monti, A., Silvestri, R.: Communication in dynamic radio networks. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 205–214. ACM (2007)

19.

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. The MIT Press and McGraw-Hill Book Company, Cambridge (2001) MATH

20.

Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D., Terry, D.: Epidemic algorithms for replicated database maintenance. In: Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 1–12. ACM (1987)

21.

Dutta, C., Pandurangan, G., Rajaraman, R., Sun, Z., Viola, E.: On the complexity of information spreading in dynamic networks. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 717–736. SIAM (2013)

22.

Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17(3), 449–467 (1965) MathSciNetCrossRefMATH

23.

Erlebach, T., Hoffmann, M., Kammer, F.: On temporal graph exploration. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 444–455. Springer, Heidelberg (2015) CrossRef

24.

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

25.

Fleischer, L., Tardos, É.: Efficient continuous-time dynamic network flow algorithms. Oper. Res. Lett. 23(3), 71–80 (1998) MathSciNetCrossRefMATH

26.

Flocchini, P., Mans, B., Santoro, N.: Exploration of periodically varying graphs. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 534–543. Springer, Heidelberg (2009) CrossRef

27.

Gharan, S.O., Saberi, A., Singh, M.: A randomized rounding approach to the traveling salesman problem. In: Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 550–559. IEEE Computer Society, Washington, DC (2011). http://dx.doi.org/10.1109/FOCS.2011.80

28.

Haeupler, B., Kuhn, F.: Lower bounds on information dissemination in dynamic networks. In: Aguilera, M.K. (ed.) DISC 2012. LNCS, vol. 7611, pp. 166–180. Springer, Heidelberg (2012) CrossRef

29.

Halldórsson, M.M.: Approximating discrete collections via local improvements. In: Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 160–169. Society for Industrial and Applied Mathematics (1995)

30.

Harary, F., Gupta, G.: Dynamic graph models. Math. Comput. Model. 25(7), 79–87 (1997) MathSciNetCrossRefMATH

31.

Hedetniemi, S.M., Hedetniemi, S.T., Liestman, A.L.: A survey of gossiping and broadcasting in communication networks. Networks 18(4), 319–349 (1988) MathSciNetCrossRefMATH

32.

Holme, P., Saramäki, J.: Temporal networks. Phys. Rep. 519(3), 97–125 (2012) CrossRef

33.

Karp, R., Schindelhauer, C., Shenker, S., Vocking, B.: Randomized rumor spreading. In: Proceedings of the IEEE 41st Annual Symposium on Foundations of Computer Science (FOCS), pp. 565–574. IEEE (2000)

34.

Karpinski, M., Schmied, R.: On improved inapproximability results for the shortest superstring and related problems. In: Proceedings of 19th CATS, pp. 27–36 (2013)

35.

Kempe, D., Kleinberg, J.: Protocols and impossibility results for gossip-based communication mechanisms. In: Proceedings of the IEEE 43rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 471–480. IEEE (2002)

36.

Kempe, D., Kleinberg, J., Kumar, A.: Connectivity and inference problems for temporal networks. In: Proceedings of the 32nd annual ACM symposium on Theory of computing (STOC), pp. 504–513 (2000). http://doi.acm.org/10.1145/335305.335364

37.

Kontogiannis, S., Michalopoulos, G., Papastavrou, G., Paraskevopoulos, A., Wagner, D., Zaroliagis, C.: Analysis and experimental evaluation of time-dependent distance oracles. In: Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 147–158 (2015)

38.

Kontogiannis, S., Zaroliagis, C.: Distance oracles for time-dependent networks. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 713–725. Springer, Heidelberg (2014)

39.

Kostakos, V.: Temporal graphs. Phys. A Stat. Mech. Appl. 388(6), 1007–1023 (2009) MathSciNetCrossRef

40.

Krumke, S.O., Wirth, H.C.: On the minimum label spanning tree problem. Inf. Process. Lett. 66(2), 81–85 (1998) MathSciNetCrossRefMATH

41.

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, New York (2010). http://doi.acm.org/10.1145/1806689.1806760

42.

Kuhn, F., Oshman, R.: Dynamic networks: models and algorithms. SIGACT News 42, 82–96 (2011). http://doi.acm.org/10.1145/1959045.1959064 (Distributed Computing Column, Editor: Idit Keidar)

43.

Leighton, F.T.: Introduction to Parallel Algorithms and Architectures, vol. 188. Morgan Kaufmann, San Francisco (1992) MATH

44.

Mans, B., Mathieson, L.: On the treewidth of dynamic graphs. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol. 7936, pp. 349–360. Springer, Heidelberg (2013) CrossRef

45.

Menger, K.: Zur allgemeinen kurventheorie. Fundamenta Mathematicae 10(1), 96–115 (1927) MATH

46.

Mertzios, G.B., Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Temporal network optimization subject to connectivity constraints. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part II. LNCS, vol. 7966, pp. 657–668. Springer, Heidelberg (2013) CrossRef

47.

Mertzios, G.B., Michail, O., Spirakis, P.G.: Temporal network optimization subject to connectivity constraints. CoRR abs/1502.04382 (2015), full version of [MMCS13]

48.

Micali, S., Vazirani, V.V.: An \({O}(\sqrt{|{V}|}\cdot |{E}|)\) algorithm for finding maximum matching in general graphs. In: Proceedings of the IEEE 21st Annual Symposium on Foundations of Computer Science (FOCS), pp. 17–27. IEEE (1980)

49.

Michail, O.: Terminating distributed construction of shapes and patterns in a fair solution of automata. In: Proceedings of the 34th ACM Symposium on Principles of Distributed Computing (PODC) (2015) (to appear)

50.

Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Mediated population protocols. Theor. Comput. Sci. 412(22), 2434–2450 (2011). http://dx.doi.org/10.1016/j.tcs.2011.02.003 MathSciNetCrossRefMATH

51.

Michail, O., Chatzigiannakis, I., Spirakis, P.G.: New Models for Population Protocols. In: ynch, N.A. (ed.) Synthesis Lectures on Distributed Computing Theory. Morgan and Claypool (2011)

52.

Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Naming and counting in anonymous unknown dynamic networks. In: Higashino, T., Katayama, Y., Masuzawa, T., Potop-Butucaru, M., Yamashita, M. (eds.) SSS 2013. LNCS, vol. 8255, pp. 281–295. Springer, Heidelberg (2013) CrossRef

53.

Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Causality, influence, and computation in possibly disconnected synchronous dynamic networks. J. Parallel Distrib. Comput. 74(1), 2016–2026 (2014) CrossRefMATH

54.

Michail, O., Spirakis, P.G.: Unpublished work on random temporal graphs (2012)

55.

Michail, O., Spirakis, P.G.: Simple and efficient local codes for distributed stable network construction. In: Proceedings of the 33rd ACM Symposium on Principles of Distributed Computing (PODC), pp. 76–85. ACM (2014). http://doi.acm.org/10.1145/2611462.2611466

56.

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)

57.

Molloy, M., Reed, B.: Graph Colouring and the Probabilistic Method, vol. 23. Springer, Heidelberg (2002) MATH

58.

Monnot, J.: The labeled perfect matching in bipartite graphs. Inf. Process. Lett. 96(3), 81–88 (2005) MathSciNetCrossRefMATH

59.

O’Dell, R., Wattenhofer, R.: Information dissemination in highly dynamic graphs. In: Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), pp. 104–110 (2005). http://doi.acm.org/10.1145/1080810.1080828

60.

Orlin, J.B.: The complexity of dynamic languages and dynamic optimization problems. In: Proceedings of the 13th Annual ACM Symposium on Theory of Computing (STOC), pp. 218–227. ACM (1981)

61.

Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18(1), 1–11 (1993) MathSciNetCrossRefMATH

62.

Peleg, D.: Distributed computing: a locality-sensitive approach. SIAM Monographs on Discrete Mathematics and Applications, p. 5 (2000)

63.

Pittel, B.: On spreading a rumor. SIAM J. Appl. Math. 47(1), 213–223 (1987) MathSciNetCrossRefMATH

64.

Ravi, R.: Rapid rumor ramification: approximating the minimum broadcast time. In: Proceedings of the IEEE 35th Annual Symposium on Foundations of Computer Science (FOCS), pp. 202–213. IEEE (1994)

65.

Scheideler, C.: Models and techniques for communication in dynamic networks. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol. 2285, p. 27. Springer, Heidelberg (2002) CrossRef

66.

Tanimoto, S.L., Itai, A., Rodeh, M.: Some matching problems for bipartite graphs. J. ACM 25(4), 517–525 (1978) MathSciNetCrossRefMATH

67.

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

Titel

An Introduction to Temporal Graphs: An Algorithmic Perspective

Buch

Algorithms, Probability, Networks, and Games

Print ISBN: 978-3-319-24023-7

Electronic ISBN: 978-3-319-24024-4

https://doi.org/10.1007/978-3-319-24024-4

DOI

https://doi.org/10.1007/978-3-319-24024-4_18

Autor:

Othon Michail

Verlag

Springer International Publishing

Sequenznummer

Premium Partner

Bildnachweise