Application of statistical mechanics to combinatorial optimization problems: the chromatic number problem and \(q\)-partitioning of a graph.

DOI10.1007/BF01019685zbMath1084.05502MaRDI QIDQ1963592

Yadin Y. Goldschmidt, Pik-Yin Lai

Publication date: 2 February 2000

Published in: Journal of Statistical Physics (Search for Journal in Brave)

zbMATH Keywords

graph coloringgraph partitioningPotts modelspin glassNP-complete optimization problems

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30) Coloring of graphs and hypergraphs (05C15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

Optimal segmentation of directed graph and the minimum number of feedback arcs ⋮ The scaling of the minimum sum of edge lengths in uniformly random trees ⋮ Phase transitions in optimized network models

Cites Work

• Statistical Mechanical Theory of a Random Ferromagnetic System
• Application of statistical mechanics to NP-complete problems in combinatorial optimisation
• Cliques in random graphs
• Determining the Chromatic Number of a Graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Application of statistical mechanics to combinatorial optimization problems: the chromatic number problem and \(q\)-partitioning of a graph.