Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
A Fair-Cost Analysis of the Random Neighbor Sampling Method Kapitel lesen Erstes Kapitel lesen

2022 | OriginalPaper | Buchkapitel

Finding Colorful Paths in Temporal Graphs

verfasst von : Riccardo Dondi, Mohammad Mehdi Hosseinzadeh

Erschienen in: Complex Networks & Their Applications X

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

The problem of finding paths in temporal graphs has been recently considered due to its many applications. In this paper we consider a variant of the problem that, given a vertex-colored temporal graph, asks for a path whose vertices have distinct colors and include the maximum number of colors. We study the approximation complexity of the problem and we provide an inapproximability lower bound. Then we present a heuristic for the problem and an experimental evaluation of our heuristic, both on synthetic and real-world graphs.

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 Experiments on F-Restricted Bi-pattern Mining
Nächstes Kapitel Quantitative Evaluation of Snapshot Graphs for the Analysis of Temporal Networks
Fußnoten
Literatur
1.
Akrida, E.C., Mertzios, G.B., Spirakis, P.G., Raptopoulos, C.L.: The temporal explorer who returns to the base. J. Comput. Syst. Sci. 120, 179–193 (2021)MathSciNetCrossRefMATH
2.
3.
Bonizzoni, P., Dondi, R., Pirola, Y.: Maximum disjoint paths on edge-colored graphs: approximability and tractability. Algorithms 6(1), 1–11 (2013)MathSciNetCrossRefMATH
4.
5.
Casteigts, A., Himmel, A., Molter, H., Zschoche, P.: Finding temporal paths under waiting time constraints. In: Cao, Y., Cheng, S., Li, M. (eds.) In: Proceeding of the 31st International Symposium on Algorithms and Computation, ISAAC 2020, pp. 30:1–30:18 (2020)
6.
Castelli, M., Dondi, R., Hosseinzadeh, M.M.: Genetic algorithms for finding episodes in temporal networks. Procedia Comput. Sci. 176, 215–224 (2020)CrossRef
7.
Choudhury, M.D., Feldman, M., Amer-Yahia, S., Golbandi, N., Lempel, R., Yu, C.: Automatic construction of travel itineraries using social breadcrumbs. In: Chignell, M.H., Toms, E.G. (eds.) HT 2010, Proceedings of the 21st ACM Conference on Hypertext and Hypermedia 13–16 2010, pp. 35–44 (2010)
8.
9.
Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2012)MATH
10.
Dondi, R., Hosseinzadeh, M.M.: Dense sub-networks discovery in temporal networks. SN Comput. Sci. 2(3), 1–11 (2021)CrossRef
11.
12.
13.
Gionis, A., Lappas, T., Pelechrinis, K., Terzi, E.: Customized tour recommendations in urban areas. In: Carterette, B., Diaz, F., Castillo, C., Metzler, D. (eds.) Seventh ACM International Conference on Web Search and Data Mining, WSDM 2014, pp. 313–322 (2014)
14.
Hagberg, A., Swart, P., S Chult, D.: Exploring network structure, dynamics, and function using NetworkX. Technical report, Los Alamos National Lab. (LANL), Los Alamos, NM (United States) (2008)
15.
16.
17.
18.
19.
Thejaswi, S., Gionis, A., Lauri, J.: Finding path motifs in large temporal graphs using algebraic fingerprints. Big Data 8(5), 335–362 (2020)CrossRef
20.
Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)CrossRefMATH
21.
Wu, H., Cheng, J., Huang, S., Ke, Y., Lu, Y., Xu, Y.: Path problems in temporal graphs. Proc. VLDB Endow. 7(9), 721–732 (2014)CrossRef
22.
Wu, H., Cheng, J., Ke, Y., Huang, S., Huang, Y., Wu, H.: Efficient algorithms for temporal path computation. IEEE Trans. Knowl. Data Eng. 28(11), 2927–2942 (2016)CrossRef
23.
Zschoche, P., Fluschnik, T., Molter, H., Niedermeier, R.: The complexity of finding small separators in temporal graphs. J. Comput. Syst. Sci. 107, 72–92 (2020)MathSciNetCrossRefMATH
24.
Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Kleinberg, J.M. (ed.) Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 21–23 2006, pp. 681–690 (2006)
Metadaten
Titel
Finding Colorful Paths in Temporal Graphs
verfasst von
Riccardo Dondi
Mohammad Mehdi Hosseinzadeh
Copyright-Jahr
2022
Buch
Complex Networks & Their Applications X

Print ISBN: 978-3-030-93408-8

Electronic ISBN: 978-3-030-93409-5

Copyright-Jahr: 2022

DOI
https://doi.org/10.1007/978-3-030-93409-5_46

Premium Partner

    Bildnachweise