  We derive computable expressions of structured backward errors of approximate
eigenelements of *-palindromic and *-anti-palindromic matrix polynomials. We
also characterize minimal structured perturbations such that approximate
eigenelements are exact eigenelements of the perturbed polynomials. We detect
structure preserving linearizations which have almost no adverse effect on the
structured backward errors of approximate eigenelements of the *-palindromic
and *-anti-palindromic polynomials.
