Simple Sublinear Algorithms for Vertex Coloring via Asymmetric Palette Sparsification
Los autores presentan un teorema de esparsificación de paleta asimétrica que, al permitir tamaños de listas variables y utilizar un algoritmo de coloreo codicioso estándar, simplifica significativamente tanto la demostración teórica como la implementación de algoritmos sublineales para el coloreo de vértices en diversos modelos de computación.