Low-exponential Algorithm for Counting the Number of Edge Cover on Simple Graphs

Jose Antonio Hernandez-Servin, J. Raymundo Marcial-Romero, Guillermo de Ita


A procedure for counting edge covers of simple graphs is presented. The procedure splits simple graphs into non-intersecting cycle graphs. This is a “low exponential” exact algorithm to count edge covers for simple graphs whose upper bound in the worst case is O(1.465575(m−n) × (m + n)), where m and n are the number of edges and nodes of the input graph, respectively.


Edge covering, graph theory, integer partition.

Full Text: PDF