On finding rainbow and colorful paths

DOI10.1016/j.tcs.2016.03.017zbMath1338.68110OpenAlexW2305816191MaRDI QIDQ266284

Łukasz Kowalik, Juho Lauri

Publication date: 13 April 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.03.017

zbMATH Keywords

computational complexitygraph algorithmscolorful pathrainbow connectivity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (8)

The rainbow Steiner tree problem ⋮ A branch-and-price-and-cut algorithm for operating room scheduling under human resource constraints ⋮ Parameterized algorithms for list \(K\)-cycle ⋮ Unnamed Item ⋮ Fine-grained complexity of rainbow coloring and its variants ⋮ Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. ⋮ Fine-Grained Complexity of Rainbow Coloring and its Variants. ⋮ Finding colorful paths in temporal graphs

Cites Work

• Unnamed Item
• On the rainbow connectivity of graphs: complexity and FPT algorithms
• Hardness and algorithms for rainbow connection
• The complexity of determining the rainbow vertex-connection of a graph
• Further hardness results on rainbow and strong rainbow connectivity
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Finding and counting vertex-colored subtrees
• Fast Witness Extraction Using a Decision Oracle
• Probably optimal graph motifs
• Color-coding
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• Parameterized Algorithms

This page was built for publication: On finding rainbow and colorful paths