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

DOI10.1007/BF01019685MaRDI QIDQ1963592zbMATH OpenFDO

Authors Pik-Yin Lai, Yadin Y. Goldschmidt

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) Coloring of graphs and hypergraphs (05C15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)

Recommendations

• Application of statistical mechanics to NP-complete problems in combinatorial optimisation
• q-partitioning of graphs with finite coordination number
• scientific article; zbMATH DE number 2247572
• Phase Transitions in Combinatorial Optimization Problems
• Some experiments with simulated annealing for coloring graphs

Cites work

• scientific article; zbMATH DE number 3856167 (Why is no real title available?)
• scientific article; zbMATH DE number 3902655 (Why is no real title available?)
• scientific article; zbMATH DE number 3482343 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Application of statistical mechanics to NP-complete problems in combinatorial optimisation
• Cliques in random graphs
• Determining the Chromatic Number of a Graph
• Statistical Mechanical Theory of a Random Ferromagnetic System

Cited in

(9)

• Phase transitions in optimized network models
• 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
• Application of statistical mechanics to NP-complete problems in combinatorial optimisation
• scientific article; zbMATH DE number 2247572 (Why is no real title available?)
• Optimized network properties in network growing models
• q-partitioning of graphs with finite coordination number
• Phase Transitions in Combinatorial Optimization Problems
• Non-equilibrium dynamics and phase transitions in Potts model and interacting Ehrenfest urn model

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

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