Symmetry breaking depending on the chromatic number or the neighborhood growth

DOI10.1016/j.tcs.2012.09.004zbMath1416.68140MaRDI QIDQ392191

Mohammad Hasan, H. S. Yoon

Publication date: 13 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.09.004

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68R10: Graph theory (including graph drawing) in computer science

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68W20: Randomized algorithms

68W15: Distributed algorithms