Physics – Condensed Matter – Disordered Systems and Neural Networks
Scientific paper
2006-02-06
A.K. Hartmann and M. Weigt, Phase Transitions in Combinatorial Optimization Problems, (Wiley-VCH, Berlin, Weinheim 2005), ISBN
Physics
Condensed Matter
Disordered Systems and Neural Networks
45 pages, with permission of Wiley-VCH, see http://www.wiley.com
Scientific paper
Graph theory provides fundamental concepts for many fields of science like statistical physics, network analysis and theoretical computer science. Here we give a pedagogical introduction to graph theory, divided into three sections. In the first, we introduce some basic notations and graph theoretical problems, e.g. Eulerian circuits, vertex covers, and graph colorings. The second section describes some fundamental algorithmic concepts to solve basic graph problems numerically, as, e.g., depth-first search, calculation of strongly connected components, and minimum-spanning tree algorithms. The last section introduces random graphs and probabilistic tools to analyze the emergence of a giant component and a giant q-core in these graphs. The presented text is published as the third chapter of the book "Phase Transitions in Combinatorial Optimization Problem" (Wiley-VCH 2005). Together with introductions to algorithms, to complexity theory and to basic statistical mechanics over random structures, it provides the technical basis for the more advanced chapters. These cover the analysis of phase transitions in combinatorial optimization problems, algorithmic and analytical approaches based on statistical physics tools (replica and cavity methods), the analysis of various search algorithms and the development of efficient heuristic algorithms, based on message passing techniques (warning, belief, and survey propagation).
Hartmann Alexander K.
Weigt Martin
No associations
LandOfFree
Introduction to graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Introduction to graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Introduction to graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-730470