USING NETWORK-FLOW TECHNIQUES TO SOLVE AN OPTIMIZATION PROBLEM FROM SURFACE-PHYSICS

The solid-on-solid model provides a commonly used framework for the de scription of surfaces. In recent it has been extended in order to inve stigate the effect of defects in the bulk on the roughness of the surf ace. The determination of the ground state of this model leads to a co mbinatorial problem, which is reduced to an uncapacitated, convex mini mum-circulation problem. We will show that the successive shortest pat h algorithm solves the problem in polynomial time.