Simple Sublinear Algorithms for Vertex Coloring via Asymmetric Palette Sparsification
Die Autoren stellen einen vereinfachten Beweis für das asymmetrische Palette-Sparsifizierungs-Theorem vor, das durch die Verwendung des Standard-Greedy-Färbungsalgorithmus effizientere und leichtere sublineare Algorithmen für die -Knotenfärbung in verschiedenen Modellen ermöglicht.