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. 18, 2025
Filed:
Oct. 26, 2022
Synopsys, Inc., Mountain View, CA (US);
Olivier Rene Coudert, Sunnyvale, CA (US);
Krishanu Debnath, Bangalore, IN;
Synopsys, Inc., Sunnyvale, CA (US);
Abstract
Disclosed is a configuration to compute weakly connected components (WCCs) in a parallel, scalable and deterministic manner. The configuration receives an undirected original graph having vertices and edges. An undefined value is assigned to all the vertices of the graph. Thereafter, each vertex is visited and assigned a WCCID (index to identify a WCC). The visitation of vertices may determine whether there are one or more thread collisions. A collision is when two threads attempt to identify the same WCC. From these collisions a new graph may be generated, a collision graph, on which the same algorithm is iterated to compute WCCs of that collision graph. The process is iterated until no further collisions are determined. In a post process, the configuration merges the WCCIDs of the collision graphs to produce the WCCIDs of the original graph.