scientific article; zbMATH DE number 3978858

From MaRDI portal
Publication:3743142





[For the entire collection see Zbl 0595.00027.] A general principle was elaborated to apply thermodynamically motivated strategies on NP-complete subgraph optimization problems with given placing requirements for subsets of vertices. Such problems arise for example in the area of automation equipment, integrated circuit and computer network layout where wiring problems are important. The thermodynamically motivated strategy is a stochastic optimization algorithm by simulated annealing of ideal gases. For fixed temperature T it is a finite homogeneous Markov chain, which converges to the Boltzmann distribution under certain assumptions. It is proved that the sequence of Boltzmann distributions for \(T\to 0\) converges to all optimal solutions equally distributed and all other feasible solutions are reached with probability 0. Besides, some remarks on the speed of convergence are given. An interactive FORTRAN program package for solving the Steiner tree problem and the optimization of interacting paths systems with the help of thermodynamically motivated simulation was developed. Computing resuls for graphs up to 600 vertices are presented including a comparison with a greedy algorithm.











This page was built for publication:

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