A pedigree-based algorithm for finding efficient peeling sequences.
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.
Harbron
C
C
Rowett Research Institute, Aberdeen, Scotland, UK.
D000017:ABO Blood-Group System / Q000235:genetics; D000465:Algorithms; D001266:Atlantic Islands; D005190:Family; D005260:Female; D005838:Genotype; D006801:Humans; D008297:Male; D008433:Mathematics; D008957:Models, Genetic; D015233:Models, Statistical; D010375:Pedigree; D011336:Probability
D000017:ABO Blood-Group System