Locality based graph coloring
DOI10.1145/167088.167156zbMATH Open1310.05099OpenAlexW2065967498MaRDI QIDQ5248487FDOQ5248487
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
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)
