  In this paper, we consider interpolation by \textit{completely monotonous}
polynomials (CMPs for short), that is, polynomials with non-negative real
coefficients. In particular, given a finite set $S\subset \mathbb{R}_{>0}
\times \mathbb{R}_{\geq 0}$, we consider \textit{the minimal polynomial} of
$S$, introduced by Berg [1985], which is `minimal,' in the sense that it is
eventually majorized by all the other CMPs interpolating $S$. We give an upper
bound of the degree of the minimal polynomial of $S$ when it exists.
Furthermore, we give another algorithm for computing the minimal polynomial of
given $S$ which utilizes an order structure on sign sequences. Applying the
upper bound above, we also analyze the computational complexity of algorithms
for computing minimal polynomials including ours.
