I know that the algorithm used to generate the Brainpool curves and the NIST curves is published. The algorithm should be this one (RFC5639 Appendix A). From what it looks like it's rather slow to find secure parameters.
After some research I've also found "Efficient Algorithms for Generating Elliptic Curves over Finite Fields Suitable for Use in Cryptography" by Harald Baier (in fact it's a PhD thesis I think) on the generation of secure elliptic curves. I've also googled around and found a tool that actually generates such curves (using this algorithm I think). From an efficiency point of view this algorithm looks faster than the NIST's one.
Now my question:
Are the above two algorithms the only ones (published) for generating safe elliptic curves or are there other ones?