Finding colorful paths in temporal graphs

DOI10.1007/978-3-030-93409-5_46MaRDI QIDQ2086641zbMATHOpenAlexFDO

Authors Riccardo Dondi, M. M. Hosseinzadeh

Publication date 25 October 2022

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

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)

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.

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

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)

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

Describes a project that uses

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)