Algebraic graph theory for the formation of suboptimal cycle bases; an efficient force method

Abstract

An efficient algorithm is presented for the formation of suboptimal cycle bases of graphs corresponding to sparse cycle adjacency matrices, leading to the formation of highly sparse flexibility matrices. The algorithm presented employs concepts from the algebraic graph theory, together with a Greedy type algorithm to select cycles with small overlaps and uses a simple graph-theoretical method for controlling the independence of the selected cycles. Application of the present algorithm is extended to the formation of cycle bases corresponding to well conditioned flexibility matrices.