A pedigree-based algorithm for finding efficient peeling sequences.

Abstract

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.