Locality based graph coloring

DOI10.1145/167088.167156MaRDI QIDQ5248487zbMATH OpenOpenAlexFDO

Authors Sundar Vishwanathan, Mario Szegedy

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

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

Cited in

(19)

• On the extremal combinatorics of the Hamming space
• Linial for lists
• Combinatorial algorithms for distributed graph coloring
• Local 7-coloring for planar subgraphs of unit disk graphs
• Toward more localized local algorithms: removing assumptions concerning global knowledge
• Improved algorithms for group testing with inhibitors
• Exact bounds for distributed graph colouring
• Neighborhood graphs and distributed Δ+1-coloring
• The role of a-priori information in networks of rational agents
• Distributed deterministic edge coloring using bounded neighborhood independence
• A distributed low tree-depth decomposition algorithm for bounded expansion classes
• Improved dynamic colouring of sparse graphs
• Local conflict coloring revisited: Linial for lists
• Self-stabilizing ( +1)-coloring in sublinear (in ) rounds via locally-iterative algorithms
• Coloring chains for compression with uncertain priors
• Locally-iterative (+1)-coloring in sublinear (in ) rounds
• Distributed edge coloring in time polylogarithmic in \({\Delta }\)
• Coding for a multiple access OR channel: A survey
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition

This page was built for publication: Locality based graph coloring

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