Harbron C
Rowett Research Institute, Aberdeen, Scotland, UK.
IMA J Math Appl Med Biol. 1995;12(1):13-27. doi: 10.1093/imammb/12.1.13.
The computational cost, in terms of both storage requirements and calculation required, of performing an elimination ordering on a graph is considered as a function of the order in which the vertices of the moral graph are eliminated. Useful properties of the moral graph of a pedigree with respect to vertex elimination are observed and these properties extended to define a k-pedigree as a graph permitting allocation of one of k sexes to each vertex of the graph, such that the subgraph induced by vertices of a single six contains no cycles. Properties of k-pedigrees include an upper bound of 2k on clique size. A novel algorithm, SEXY, based upon these properties is proposed and its performance compared with other algorithms used to generate elimination sequences. It is found to give a widely dispersed range of of sequences, including some sequences requiring under a quarter of the storage and under a half of the computational time than had previously been found using standard methods.
