On the rainbow connectivity of graphs: complexity and FPT algorithms

DOI10.1007/s00453-012-9689-4zbMath1290.68060OpenAlexW1990357129MaRDI QIDQ378215

Kei Uchizawa, Takanori Aoki, Xiao Zhou, Akira Suzuki, Takehiro Ito

Publication date: 11 November 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9689-4

zbMATH Keywords

fixed parameter tractabilityseries-parallel graphcactusouterplanar graphrainbow coloring

Mathematics Subject Classification ID

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

Related Items (19)

On finding rainbow and colorful paths ⋮ Hardness results for total rainbow connection of graphs ⋮ Some results on the total proper \(k\)-connection number ⋮ On the Fine-Grained Complexity of Rainbow Coloring ⋮ Total rainbow connection number and complementary graph ⋮ On the complexity of rainbow coloring problems ⋮ Rainbow total-coloring of complementary graphs and Erdős-Gallai type problem for the rainbow total-connection number ⋮ Graphs with small total rainbow connection number ⋮ The rainbow Steiner tree problem ⋮ An integer program and new lower bounds for computing the strong rainbow connection numbers of graphs ⋮ Further hardness results on rainbow and strong rainbow connectivity ⋮ Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs ⋮ On total rainbow \(k\)-connected graphs ⋮ Complexity of rainbow vertex connectivity problems for restricted graph classes ⋮ Total rainbow connection numbers of some special graphs ⋮ (Strong) total proper connection of some digraphs ⋮ Generalized rainbow connectivity of graphs ⋮ Fine-grained complexity of rainbow coloring and its variants ⋮ Fine-Grained Complexity of Rainbow Coloring and its Variants.

Cites Work

• Hardness and algorithms for rainbow connection
• The complexity of determining the rainbow vertex-connection of a graph
• On rainbow connection
• The parameterized complexity of some minimum label problems
• New Hardness Results in Rainbow Connectivity
• The rainbow connectivity of a graph
• On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms
• Rainbow connection in graphs
• Graph Classes: A Survey
• Color-coding
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• Unnamed Item
• Unnamed Item

This page was built for publication: On the rainbow connectivity of graphs: complexity and FPT algorithms