Estimating the relevance on Communication Lines Based on the Number of Edge Covers

Counting the number of edge covers on graphs, denoted as the #Edge_Covers problem, is a #P-complete problem. Knowing the number of edge covers is useful for estimating the relevance of the lines in a communication network, which is an important measure in the reliability analysis of a network. In this paper, we present efficient algorithms for solving the #Edge_Covers problem on the most common network topologies, namely, Bus, Stars, Trees and Rings. We show that if the topology of the network G does not contain intersecting cycles (any pair of cycles with common edges), then the number of edge covers can be computed in linear time on the size of G.