Generation of K-Trees of undirected graphs

Evaluating the reliability of a network with multiple sources and multiple terminals and unreliable vertices and edges can be converted into a single-source problem and solved using K-Trees. This paper presents an efficient algorithm (GenK-Trees) for enumerating all the K-Trees in an undirected graph. This is the first algorithm with polynomial complexity per K-Tree generated. Formal proofs of the correctness of GenK-Trees and its complexity are given. GenK-Trees is computationally simple, and easy to understand and program; its memory requirements are small, and so it can handle large graphs without running into memory limitations