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

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

Cited in

(17)

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

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)