Fine-Grained Complexity of Rainbow Coloring and its Variants.
DOI10.4230/LIPICS.MFCS.2017.60zbMATH Open1441.68158OpenAlexW2771470748MaRDI QIDQ5111276FDOQ5111276
Publication date: 26 May 2020
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8099/pdf/LIPIcs-MFCS-2017-60.pdf/
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Title not available (Why is that?)
- On rainbow connection
- Which problems have strongly exponential complexity?
- Rainbow connections of graphs: a survey
- On finding rainbow and colorful paths
- Rainbow connection in graphs
- On the rainbow connectivity of graphs: complexity and FPT algorithms
- Title not available (Why is that?)
- Color-coding
- Title not available (Why is that?)
- Hardness and algorithms for rainbow connection
- Parameterized Algorithms
- On the complexity of \(k\)-SAT
- Chromatic graph theory
- Rainbow connectivity: hardness and tractability
- Title not available (Why is that?)
- Rainbow Colouring of Split and Threshold Graphs
- Inapproximability of Rainbow Colouring
- An upper bound for the harmonious chromatic number of a graph
- On the Fine-Grained Complexity of Rainbow Coloring
- Title not available (Why is that?)
- Tight Running Time Lower Bounds for Vertex Deletion Problems
- Upper bounds for harmonious colorings
- Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
Cited In (5)
This page was built for publication: Fine-Grained Complexity of Rainbow Coloring and its Variants.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111276)
