List colouring trees in logarithmic space

DOI10.4230/LIPICS.ESA.2022.24MaRDI QIDQ6969661zbMATH OpenFDO

Authors Hans L. Bodlaender, Carla Groenland, H. Jacob

Publication date 19 June 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2022.24

zbMATH Keywords

graph algorithmslist colouringlogspacespace complexitytree-partition-widthtrees

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• Complexity of list coloring problems with a fixed total number of colors
• Computational Complexity
• Generalized coloring for tree-like graphs
• scientific article; zbMATH DE number 3917707 (Why is no real title available?)
• scientific article; zbMATH DE number 7803587 (Why is no real title available?)
• Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
• Logspace versions of the theorems of Bodlaender and Courcelle
• On space efficiency of algorithms working on structural decompositions of graphs
• On the complexity of some colorful problems parameterized by treewidth
• On the space and circuit complexity of parameterized problems: classes and completeness
• On tree-partition-width
• On tree-partitions of graphs
• Parameterized problems complete for nondeterministic FPT time and logarithmic space
• Some results on tree decomposition of graphs
• Space complexity of list H-colouring: a dichotomy
• Undirected connectivity in log-space
• Width, depth, and space: tradeoffs between branching and dynamic programming
• Width-parametrized SAT: time-space tradeoffs

Cited in

(2)

• XALP-completeness of parameterized problems on planar graphs
• Precoloring extension with demands on paths

This page was built for publication: List colouring trees in logarithmic space

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