The problem of robust stability of linear lime-invariant systems in state-space models is considered. An iterative algorithm based on frequency domain approach is proposed which leads to new stability robustness measures. The case of structural perturbations is considered and the new bounds are shown to be a significant improvement over recent ones reported. In addition, it is shown that the directional information on structured perturbations can easily be incorporated in the new robustness criterion. Several illustrative examples are worked out.