Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space
It is shown that the problem of 2-colouring a linked list is complete for deterministic log-space under \(NC^ 1\) reductions.
scientific article; zbMATH DE number 540909
scientific article