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.

(2022). Finding Colorful Paths in Temporal Graphs . Retrieved from https://hdl.handle.net/10446/233876

Finding Colorful Paths in Temporal Graphs

Dondi, Riccardo;Hosseinzadeh, Mohammad Mehdi
2022-01-01

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.
Dondi, Riccardo; Hosseinzadeh, Mohammad Mehdi
File allegato/i alla scheda:
File Dimensione del file Formato  
ComplexNetworks202122.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 266.65 kB
Formato Adobe PDF
266.65 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/233876
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact