The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Nov. 03, 2015
Filed:
Aug. 28, 2013
Oracle International Corporation, Redwood City, CA (US);
Ashutosh Chakraborty, Austin, TX (US);
Wonjoon Choi, Austin, TX (US);
Duo Ding, Austin, TX (US);
Rajendran Panda, Round Rock, TX (US);
Oracle International Corporation, Redwood City, CA (US);
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.