scientific article; zbMATH DE number 3978858
[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.
- A thermodynamically motivated simulation procedure for combinatorial optimization problems
- scientific article; zbMATH DE number 3917752
- scientific article; zbMATH DE number 3970752
- Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
- Optimal subgraph structures in scale-free configuration models
- Using simulated annealing to construct extremal graphs
- \textit{Physarum}-inspired applications in graph-optimization problems
- A simulated annealing algorithm for the maximum planar subgraph problem
- scientific article; zbMATH DE number 49060
- scientific article; zbMATH DE number 3917751 (Why is no real title available?)
- scientific article; zbMATH DE number 3917752 (Why is no real title available?)
- scientific article; zbMATH DE number 3967815 (Why is no real title available?)
- scientific article; zbMATH DE number 3970752 (Why is no real title available?)
- A Comparison of Two Simulated Annealing Algorithms Applied to the Directed Steiner Problem on Networks
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)