Finding colorful paths in temporal graphs

DOI10.1007/978-3-030-93409-5_46zbMATH Open1506.05198OpenAlexW4205689001MaRDI QIDQ2086641FDOQ2086641

Authors: Riccardo Dondi, M. M. Hosseinzadeh 

Publication date: 25 October 2022

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.

Full work available at URL: https://arxiv.org/abs/2109.01392

Recommendations

• Sliding window temporal graph coloring
• On finding rainbow and colorful paths
• Coloring temporal graphs
• scientific article; zbMATH DE number 2147947
• Maximum disjoint paths on edge-colored graphs: approximability and tractability

zbMATH Keywords

heuristicsapproximation complexitytemporal graphsalgorithms on graphsalgorithms for network analysis

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Cites Work

• Color-coding
• Edge exploration of temporal graphs
• Finding temporal paths under waiting time constraints
• Graph theory
• Königsberg sightseeing: Eulerian walks in temporal graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Maximum disjoint paths on edge-colored graphs: approximability and tractability
• On finding rainbow and colorful paths
• The complexity of finding small separators in temporal graphs
• The design of approximation algorithms
• The temporal explorer who returns to the base
• Tropical paths in vertex-colored graphs

Cited In (5)

• Sliding window temporal graph coloring
• Coloring temporal graphs
• The structural complexity landscape of finding balance-fair shortest paths
• Finding temporal paths under waiting time constraints
• Untangling temporal graphs of bounded degree

Uses Software

• NetworkX
• SNAP

This page was built for publication: Finding colorful paths in temporal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2086641)