Skip to main content

Phase Transitions in Combinatorial Optimization Problems: Basics, Algorithms and Statistical Mechanics

Phase Transitions in Combinatorial Optimization Problems: Basics, Algorithms and Statistical Mechanics

Alexander K. Hartmann, Martin Weigt

ISBN: 978-3-527-60686-3

May 2006

360 pages

$140.99

Description

A concise, comprehensive introduction to the topic of statistical physics of combinatorial optimization, bringing together theoretical concepts and algorithms from computer science with analytical methods from physics. The result bridges the gap between statistical physics and combinatorial optimization, investigating problems taken from theoretical computing, such as the vertex-cover problem, with the concepts and methods of theoretical physics.
The authors cover rapid developments and analytical methods that are both extremely complex and spread by word-of-mouth, providing all the necessary basics in required detail. Throughout, the algorithms are shown with examples and calculations, while the proofs are given in a way suitable for graduate students, post-docs, and researchers. Ideal for newcomers to this young, multidisciplinary field.
Algorithms
Introduction to Graphs
Introduction to Complexity Theory
Statistical Mechanics of the Ising Model
Algorithms and Numerical Results for Vertex Covers
Statistical Mechanics of Vertex-covers on a Random Graph
The Dynamics of Vertex-cover Algorithms
Towards new, Statistical-mechanics Motivated Algorithms
The Satisfiability Problem
Optimization Problems in Physics
"This new book is a concise, comprehensive introduction to the topic of statistical physics of combinatorial optimization, bringing together theoretical concepts and algorithms from computer science with analytical methods from physics."
Metall

"A well-balanced, concise yet comprehensive introduction, combining statistical physics and combinatorial optimization."
Zeitschrift für Kristallographie