Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Temporal Flows in Temporal Networks

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 10236))

Included in the following conference series:

Abstract

We introduce temporal flows on temporal networks [17,19], i.e., networks the links of which exist only at certain moments of time. Such networks are ephemeral in the sense that no link exists after some time. Our flow model is new and differs from the “flows over time” model, also called “dynamic flows” in the literature. We show that the problem of finding the maximum amount of flow that can pass from a source vertex\({s}\) to a sink vertex\({t}\) up to a given time is solvable in Polynomial time, even when node buffers are bounded. We then examine mainly the case of unbounded node buffers. We provide a simplified staticTime-Extended network (\(\mathrm {STEG}\)), which is ofpolynomial size to the input and whose static flow rates are equivalent to the respective temporal flow of the temporal network; using\(\mathrm {STEG}\), we prove that the maximum temporal flow is equal to the minimumtemporal\({s}\text {-}{t}\)cut. We further show that temporal flows can always be decomposed into flows, each of which moves only through a journey, i.e., a directed path whose successive edges have strictly increasing moments of existence. We partially characterise networks with random edge availabilities that tend to eliminate the\({s}\rightarrow {t}\) temporal flow. We then considermixed temporal networks, which have some edges with specified availabilities and some edges with random availabilities; we show that it is#P-hard to compute thetails and expectations of the maximum temporal flow (which is now a random variable) in a mixed temporal network.

This work was partially supported by (i) the School of EEE and CS and the NeST initiative of the University of Liverpool, (ii) the NSERC Discovery grant, (iii) the Polish National Science Center grant DEC-2011/02/A/ST6/00201, and (iv) the FET EU IP Project MULTIPLEX under contract No. 317532.

Due to lack of space, an extended literature review and all missing proofs can be found in the full version of this paper athttp://arxiv.org/abs/1606.01091 [2].

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Similar content being viewed by others

Notes

  1. 1.

    The first “dynamic” term refers to the dynamic nature of the underlying graph.

  2. 2.

    We choose an even integer to simplify the calculations in the remainder of the paper. However, with careful adjustments, the results would still hold for an arbitrary integer.

  3. 3.

    We choose an even integer to simplify the calculations. However, with careful adjustments in the calculations, the results would still hold for an arbitrary integer.

  4. 4.

    \(\{0,1\}^* = \cup _{n \ge 0} \{0,1\}^n\), where\(\{0,1\}^n\) is the set of all strings (of bits 0, 1) of lengthn.

References

  1. Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall Inc., Upper Saddle River (1993)

    MATH  Google Scholar 

  2. Akrida, E.C., Czyzowicz, J., Gasieniec, L., Kuszner, L., Spirakis, P.G.: Flows in temporal networks. CoRR abs/1606.01091 (2016)

    Google Scholar 

  3. Akrida, E.C., Gasieniec, L., Mertzios, G.B., Spirakis, P.G.: Ephemeral networks with random availability of links: the case of fast networks. J. Parallel Distrib. Comput.87, 109–120 (2016)

    Article  Google Scholar 

  4. Akrida, E.C., Gąsieniec, L., Mertzios, G.B., Spirakis, P.G.: On temporally connected graphs of small cost. In: Sanità, L., Skutella, M. (eds.) WAOA 2015. LNCS, vol. 9499, pp. 84–96. Springer, Cham (2015). doi:10.1007/978-3-319-28684-6_8

    Chapter  Google Scholar 

  5. Akrida, E.C., Spirakis, P.G.: On verifying and maintaining connectivity of interval temporal networks. In: Bose, P., Gąsieniec, L.A., Römer, K., Wattenhofer, R. (eds.) ALGOSENSORS 2015. LNCS, vol. 9536, pp. 142–154. Springer, Cham (2015). doi:10.1007/978-3-319-28472-9_11

    Chapter  Google Scholar 

  6. Aronson, J.E.: A survey of dynamic network flows. Ann. Oper. Res.20(1–4), 1–66 (1989)

    Article MathSciNet MATH  Google Scholar 

  7. 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. LNCS, vol. 5125, pp. 121–132. Springer, Heidelberg (2008). doi:10.1007/978-3-540-70575-8_11

    Chapter  Google Scholar 

  8. Batra, J., Garg, N., Kumar, A., Mömke, T., Wiese, A.: New approximation schemes for unsplittable flow on a path. In: Indyk, P. (ed.) Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, 4–6 January 2015, pp. 47–58. SIAM (2015)

    Google Scholar 

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

    Article  Google Scholar 

  10. Chaintreau, A., Mtibaa, A., Massoulié, L., Diot, C.: The diameter of opportunistic mobile networks. In: Proceedings of the 2007 ACM Conference on Emerging Network Experiment and Technology, CoNEXT 2007, New York, NY, USA, 10–13 December 2007, p. 12 (2007)

    Google Scholar 

  11. Clementi, A.E.F., Macci, C., Monti, A., Pasquale, F., Silvestri, R.: Flooding time of edge-Markovian evolving graphs. SIAM J. Discret. Math. (SIDMA)24(4), 1694–1712 (2010)

    Article MathSciNet MATH  Google Scholar 

  12. 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). doi:10.1007/978-3-662-47672-7_36

    Google Scholar 

  13. Ford, D.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (2010)

    MATH  Google Scholar 

  14. Hoppe, B., Tardos, E.: The quickest transshipment problem. In: Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995, pp. 512–521. Society for Industrial and Applied Mathematics, Philadelphia (1995)

    Google Scholar 

  15. Hoppe, B.E.: Efficient dynamic network flow algorithms. Ph.D. thesis (1995)

    Google Scholar 

  16. Kamiyama, N., Katoh, N.: The universally quickest transshipment problem in a certain class of dynamic networks with uniform path-lengths. Discret. Appl. Math.178, 89–100 (2014)

    Article MathSciNet MATH  Google Scholar 

  17. Kempe, D., Kleinberg, J.M., 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)

    Google Scholar 

  18. Madry, A.: Fast approximation algorithms for cut-based problems in undirected graphs. In: 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, Las Vegas, Nevada, USA, 23–26 October 2010, pp. 245–254 (2010)

    Google Scholar 

  19. 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. LNCS, vol. 7966, pp. 657–668. Springer, Heidelberg (2013). doi:10.1007/978-3-642-39212-2_57

    Google Scholar 

  20. Orlin, J.B.: Max flows in O(nm) time, or better. In: Symposium on Theory of Computing Conference, STOC 2013, Palo Alto, CA, USA, 1–4 June 2013, pp. 765–774 (2013)

    Google Scholar 

  21. Papadimitriou, C.M.: Computational Complexity. Addison-Wesley, Reading (1994)

    MATH  Google Scholar 

  22. Powell, W.B., Jaillet, P., Odoni, A.: Stochastic and dynamic networks and routing. Handb. Oper. Res. Manag. Sci.8, 141–295 (1995)

    Article MathSciNet MATH  Google Scholar 

  23. Radzik, T.: Faster algorithms for the generalized network flow problem. Math. Oper. Res.23(1), 69–100 (1998)

    Article MathSciNet MATH  Google Scholar 

  24. Serna, M.J.: Randomized parallel approximations to max flow. In: Kao, M.-Y. (ed.) Encyclopedia of Algorithms, pp. 1750–1753. Springer, New York (2016)

    Chapter  Google Scholar 

  25. Skutella, M.: An introduction to network flows over time. In: Cook, W., Lovász, L., Vygen, J. (eds.) Research Trends in Combinatorial Optimization, pp. 451–482. Springer, Heidelberg (2008)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Liverpool, Liverpool, UK

    Eleni C. Akrida, Leszek Gąsieniec & Paul G. Spirakis

  2. Dépt. d’informatique, Université du Québec en Outaouais, Gatineau, QC, Canada

    Jurek Czyzowicz

  3. Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, Gdańsk, Poland

    Łukasz Kuszner

  4. Computer Technology Institute and Press “Diophantus” (CTI), Patras, Greece

    Paul G. Spirakis

Authors
  1. Eleni C. Akrida

    You can also search for this author inPubMed Google Scholar

  2. Jurek Czyzowicz

    You can also search for this author inPubMed Google Scholar

  3. Leszek Gąsieniec

    You can also search for this author inPubMed Google Scholar

  4. Łukasz Kuszner

    You can also search for this author inPubMed Google Scholar

  5. Paul G. Spirakis

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toEleni C. Akrida.

Editor information

Editors and Affiliations

  1. National Technical University of Athens, Zografou, Athens, Greece

    Dimitris Fotakis

  2. National Technical University of Athens, Zografou, Athens, Greece

    Aris Pagourtzis

  3. Université Paris-Dauphine, Paris, France

    Vangelis Th. Paschos

Rights and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

Akrida, E.C., Czyzowicz, J., Gąsieniec, L., Kuszner, Ł., Spirakis, P.G. (2017). Temporal Flows in Temporal Networks. In: Fotakis, D., Pagourtzis, A., Paschos, V. (eds) Algorithms and Complexity. CIAC 2017. Lecture Notes in Computer Science(), vol 10236. Springer, Cham. https://doi.org/10.1007/978-3-319-57586-5_5

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

[8]ページ先頭
©2009-2025 Movatter.jp