[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

Making the Interval Membership Width of Temporal Graphs Connected and Bidirectional

  • Conference paper
  • First Online:
Combinatorial Algorithms (IWOCA 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14764))

Included in the following conference series:

  • 211 Accesses

Abstract

Temporal graphs are graphs that evolve over time. Many problems which are polynomial-time solvable in standard graphs become NP-hard when appropriately defined in the realm of temporal graphs. This suggested the definition of several parameters for temporal graphs and to prove the fixed-parameter tractability of several problems with respect to these parameters. In this paper, we introduce a hierarchy of parameters based on the previously defined interval membership width and on the temporal evolution of the connected components of the underlying static graph. We then show that the Eulerian trail problem and the temporal 2-coloring problem are both fixed-parameter tractable (in short, FPT) with respect to any of the parameters in the hierarchy. We also introduce a vertex-variant of the parameters and we show that the firefighter problem (which was known to be FPT with respect to the vertex-variant of the interval membership width) is also FPT with respect to one of the parameters in the second level of the hierarchy.

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

Access this chapter

Subscribe and save

Springer+ Basic
£29.99 /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
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 51.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 69.99
Price includes VAT (United Kingdom)
  • 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

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    For every positive integer k, [k] denotes the set \(\{1,2,\ldots ,k\}\).

  2. 2.

    Similarly, one can consider non-decreasing sequences, i.e. with \(t_{1}\le \ldots \le t_{k}\). In this paper, however, we focus on the strictly increasing case.

References

  1. Bhadra, S., Ferreira, A.: Computing multicast trees in dynamic networks and the complexity of connected components in evolving graphs. J. Internet Serv. Appl. 3(3), 269–275 (2012)

    Article  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  3. Bumpus, B.M., Meeks, K.: Edge exploration of temporal graphs. Algorithmica 85(3), 688–716 (2023)

    Article  MathSciNet  Google Scholar 

  4. Calamai, M., Crescenzi, P., Marino, A.: On computing the diameter of (weighted) link streams. ACM J. Exp. Algorithmics 27, 1–28 (2022)

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  6. Casteigts, A., Himmel, A.S., Molter, H., Zschoche, P.: Finding temporal paths under waiting time constraints. Algorithmica 83, 2754–2802 (2021)

    Article  MathSciNet  Google Scholar 

  7. Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21275-3

    Book  Google Scholar 

  8. Enright, J.A., Meeks, K., Molter, H.: Counting temporal paths. In: 40th STACS. LIPIcs, vol. 254, pp. 30:1–30:19 (2023)

    Google Scholar 

  9. Finbow, S., MacGillivray, G.: The firefighter problem: a survey of results, directions and questions. Australas. J. Comb. 43, 57–78 (2009)

    MathSciNet  Google Scholar 

  10. Flocchini, P., Mans, B., Santoro, N.: Exploration of periodically varying graphs. In: International Symposium on Algorithms and Computation, pp. 534–543 (2009)

    Google Scholar 

  11. Fluschnik, T., Molter, H., Niedermeier, R., Renken, M., Zschoche, P.: As time goes by: reflections on treewidth for temporal graphs. In: Treewidth, Kernels, and Algorithms, pp. 49–77 (2020)

    Google Scholar 

  12. Hand, S.D., Enright, J.A., Meeks, K.: Making life more confusing for firefighters. In: International Conference on Fun with Algorithms, pp. 15:1–15:15 (2022)

    Google Scholar 

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

    Article  Google Scholar 

  14. Kempe, D., Kleinberg, J., Kumar, A.: Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci. 64(4), 820–842 (2002)

    Article  MathSciNet  Google Scholar 

  15. Latapy, M., Viard, T., Magnien, C.: Stream graphs and link streams for the modeling of interactions over time. Soc. Netw. Anal. Min. 8(1), 61 (2018)

    Article  Google Scholar 

  16. Marino, A., Silva, A.: Coloring temporal graphs. J. Comput. Syst. Sci. 123, 171–185 (2022)

    Article  MathSciNet  Google Scholar 

  17. Marino, A., Silva, A.: Eulerian walks in temporal graphs. Algorithmica 85(3), 805–830 (2022)

    Article  MathSciNet  Google Scholar 

  18. Michail, O.: An introduction to temporal graphs: an algorithmic perspective. Internet Math. 12, 308–343 (2015)

    MathSciNet  Google Scholar 

  19. Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. ACM 22(2), 215–225 (1975)

    Article  MathSciNet  Google Scholar 

  20. West, D.B., et al.: Introduction to graph theory, vol. 2. Prentice Hall, Upper Saddle River (2001)

    Google Scholar 

Download references

Acknowledgement

P.C. was supported by PNRR MIUR project GAMING “Graph Algorithms and MinINg for Green agents” (PE0000013, CUP D13C24000430001), A.M. by PNRR CN4 Centro Nazionale per la Mobilità Sostenibile, NextGeneration EU-CUP, B13C22001000001, by MUR of Italy, under PRIN Project n. 2022ME9Z78-NextGRAAL: Next-generation algorithms for constrained GRAph visuALization, and by PRIN PNRR Project n. P2022NZPJA-DLT-FRUIT: A user centered framework for facilitating DLTs FRUITion, A.S. by CNPq 303803/2020-7, 404479/2023-5, FUNCAP MLC-0191-00056.01.00/22, COFECUB 88887.712023/2022-00, and D.M.T. by the French-German Collaboration ANR/DFG Project UTMA (ANR-20-CE92-0027) and by the MEAE and the MESR, via the Franco-Norwegian project PHC Aurora projet n. 51260WL (2024).

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Ana Silva .

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Christodoulou, F., Crescenzi, P., Marino, A., Silva, A., Thilikos, D.M. (2024). Making the Interval Membership Width of Temporal Graphs Connected and Bidirectional. In: Rescigno, A.A., Vaccaro, U. (eds) Combinatorial Algorithms. IWOCA 2024. Lecture Notes in Computer Science, vol 14764. Springer, Cham. https://doi.org/10.1007/978-3-031-63021-7_19

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-63021-7_19

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-63020-0

  • Online ISBN: 978-3-031-63021-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics