On finding rainbow and colorful paths

DOI10.1016/J.TCS.2016.03.017zbMATH Open1338.68110OpenAlexW2305816191MaRDI QIDQ266284FDOQ266284

Authors: Ł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

Recommendations

• Fine-grained complexity of rainbow coloring and its variants
• Fine-Grained Complexity of Rainbow Coloring and its Variants.
• On the fine-grained complexity of rainbow coloring
• On the fine-grained complexity of rainbow coloring

zbMATH Keywords

computational complexitygraph algorithmscolorful pathrainbow connectivity

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• 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
• On the rainbow connectivity of graphs: complexity and FPT algorithms
• Color-coding
• Hardness and algorithms for rainbow connection
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• Parameterized algorithms
• The complexity of determining the rainbow vertex-connection of a graph
• Further hardness results on rainbow and strong rainbow connectivity

Cited In (11)

• Simultaneous time-space upper bounds for red-blue path problem in planar DAGs
• Title not available (Why is that?)
• Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
• A branch-and-price-and-cut algorithm for operating room scheduling under human resource constraints
• Finding colorful paths in temporal graphs
• Fine-Grained Complexity of Rainbow Coloring and its Variants.
• The rainbow Steiner tree problem
• Fixed-parameter tractability of maximum colored path and beyond
• Parameterized algorithms for list \(K\)-cycle
• On the fine-grained complexity of rainbow coloring
• Fine-grained complexity of rainbow coloring and its variants

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

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