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 Combinatorial Optimization Problems
• q-partitioning of graphs with finite coordination number
• Non-equilibrium dynamics and phase transitions in Potts model and interacting Ehrenfest urn model
• Application of statistical mechanics to NP-complete problems in combinatorial optimisation
• scientific article; zbMATH DE number 2247572 (Why is no real title available?)
• The scaling of the minimum sum of edge lengths in uniformly random trees
• Optimal segmentation of directed graph and the minimum number of feedback arcs
• Optimized network properties in network growing models
• Phase transitions in optimized network models

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)