Locality based graph coloring

DOI10.1145/167088.167156zbMath1310.05099OpenAlexW2065967498MaRDI QIDQ5248487

Sundar Vishwanathan

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167156

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

Improved algorithms for group testing with inhibitors ⋮ Neighborhood graphs and distributed Δ+1-coloring ⋮ On the extremal combinatorics of the Hamming space ⋮ Exact Bounds for Distributed Graph Colouring ⋮ Local 7-coloring for planar subgraphs of unit disk graphs ⋮ Toward more localized local algorithms: removing assumptions concerning global knowledge ⋮ Coloring chains for compression with uncertain priors ⋮ Coding for a multiple access OR channel: A survey ⋮ Combinatorial algorithms for distributed graph coloring ⋮ Unnamed Item ⋮ Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition ⋮ A distributed low tree-depth decomposition algorithm for bounded expansion classes ⋮ Distributed deterministic edge coloring using bounded neighborhood independence ⋮ Linial for lists

This page was built for publication: Locality based graph coloring