Patent ID: 7924729
Filing Date: 2011-04-12
Classification: H04L

Abstract:
1. A computer-implemented method for determining a minimum cost solution for resolving a covering-by-pairs problem given a plurality of covering nodes, a plurality of branch nodes, and a plurality of edges connecting the covering nodes and the branch nodes, the method comprising computer-implemented operations for: generating, through a computer having a processor and a memory, a plurality of vectors, each vector comprising a plurality of genes, each gene having a binary value and corresponding to one of the covering nodes, the binary value of each gene indicating whether the corresponding covering node is a selected covering node included in a proposed solution or a non-selected covering node not included in the proposed solution; for each vector in the plurality of vectors, determining, through the computer, whether the selected covering nodes cover the branch nodes; responsive to determining that the selected covering nodes do not cover the branch nodes, completing, through the computer, each vector so that the selected covering nodes cover the branch nodes; responsive to determining that selected covering nodes cover the branch nodes or to completing the vector, removing, through the computer, redundant covering nodes from each vector; inserting, through the computer, the vectors into a current population; and generating, through the computer, a new population by evolving the current population for at least one generation, the minimum cost solution comprising the vector with a lowest cost from the new population.