Space complexity of list H-colouring: a dichotomy

DOI10.1137/1.9781611973402.26zbMath1421.68073arXiv1308.0180OpenAlexW2495593369MaRDI QIDQ5383985

Arash Rafiey, Benoit Larose, László Egri, Pavol Hell

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1308.0180

Mathematics Subject Classification ID

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 (5)

Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ Unnamed Item ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ On Maltsev digraphs ⋮ Constraint Satisfaction with Counting Quantifiers

This page was built for publication: Space complexity of list H-colouring: a dichotomy