Finding colorful paths in temporal graphs

DOI10.1007/978-3-030-93409-5_46zbMATH Open1506.05198arXiv2109.01392OpenAlexW4205689001MaRDI 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

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

Cited In (3)

• Sliding window temporal graph coloring
• The structural complexity landscape of finding balance-fair shortest paths
• 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)