Finding colorful paths in temporal graphs

DOI10.1007/978-3-030-93409-5_46zbMath1506.05198arXiv2109.01392OpenAlexW4205689001MaRDI QIDQ2086641

Riccardo Dondi, Mohammad Mehdi 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

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

Related Items (2)

The structural complexity landscape of finding balance-fair shortest paths ⋮ Untangling temporal graphs of bounded degree

Uses Software

• NetworkX
• SNAP

Cites Work

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

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