Method and apparatus for minimum cost cycle removal from a directed graph
US9176732B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Aug 28, 2013 |
| Grant date | Nov 3, 2015 |
| Priority date | — |
| Expiry date | Nov 24, 2033 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F30/20
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Implementations of the present disclosure involve a system and/or method for minimum cost cycle removal from a directed graph. The system determines if a provided graph contains any cycles by assigning each vertex an integer value and comparing the integer values of vertices connected by an edge. When the value of a starting vertex is greater than an ending vertex, a cycle is present. The system then determines which edges may be removed in order to minimize the cost of breaking the cycle. The system generates a linear cost function that is equal to the sum of a cost to remove an edge multiplied by a corresponding binary variable. Constraints are generated to ensure that the result does not have any cycles. The system then solves for the minimum of the linear cost function by utilizing the constraints. The value of the binary variables may then be used to determine which edges to remove.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.