Fine-grained complexity of rainbow coloring and its variants
From MaRDI portal
Publication:2051859
DOI10.1016/j.jcss.2021.10.001zbMath1481.68033OpenAlexW3205160705MaRDI QIDQ2051859
Publication date: 25 November 2021
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8099/
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On finding rainbow and colorful paths
- On the rainbow connectivity of graphs: complexity and FPT algorithms
- Hardness and algorithms for rainbow connection
- On rainbow connection
- Which problems have strongly exponential complexity?
- Rainbow connections of graphs: a survey
- Parametrized complexity theory.
- New Hardness Results in Rainbow Connectivity
- Rainbow Colouring of Split and Threshold Graphs
- Inapproximability of Rainbow Colouring
- On the Fine-Grained Complexity of Rainbow Coloring
- Rainbow connection in graphs
- An upper bound for the harmonious chromatic number of a graph
- Upper bounds for harmonious colorings
- Color-coding
- Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
- On the Fine-Grained Complexity of Rainbow Coloring
- Tight Running Time Lower Bounds for Vertex Deletion Problems
- Parameterized Algorithms
- On the complexity of \(k\)-SAT
This page was built for publication: Fine-grained complexity of rainbow coloring and its variants
