US Patent No: 7,764,629
Number of patents in Portfolio can not be more than 2000
Identifying connected components of a graph in parallel
Stats
-
Jul 27, 2010
Issued date -
Aug 11, 2005
filing date -
11/201,765
serial no -
In Force
status
Importance
Loading Importance Indicators...
Abstract
A method and system for finding connected components of a graph using a parallel algorithm is provided. The connected nodes system performs a search algorithm in parallel to identify subgraphs of the graph in which the nodes of the subgraph are connected. The connected nodes system also identifies which subgraphs have at least one edge between their nodes. Thus, the connected nodes system effectively generates a hyper-graph with the subgraphs as hyper-nodes that are connected when subgraphs have at least one edge between their nodes. The connected nodes system may then perform a conventional connected component algorithm on the hyper-graph to identify the connected hyper-nodes, which effectively identifies the connected nodes of the underlying graphs.
Loading the Abstract Image...
First Claim
Related Publications
Loading Related Publications...
International Classification(s)
- [Classification Symbol]
- [Patents Count]
Cited Art
| Patent Info | (Count) | # Cites | Year |
|---|---|---|---|
|
|
|||
| 6,438,734 Fast search method for enabling a computer to find elementary loops in a graph | 6 | 1997 | |
|
|
|||
| 2002/0087,275 Visualization and manipulation of biomolecular relationships using graph operators | 10 | 2001 | |
|
|
|||
| 5,784,557 Method and apparatus for transforming an arbitrary topology collection of nodes into an acyclic directed graph | 66 | 1996 | |
|
|
|||
| 6,442,663 Data collection and restoration for homogeneous or heterogeneous process migration | 58 | 1998 | |
|
|
|||
| 5,170,393 Adaptive routing of messages in parallel and distributed processor systems | 50 | 1990 | |
|
|
|||
| 2006/0034,194 Identifying connected components of a graph in parallel | 4 | 2005 | |
|
|
|||
| 6,230,151 Parallel classification for data mining in a shared-memory multiprocessor system | 35 | 1998 | |
|
|
|||
| 5,732,072 Method for adaptive routing in a communication network | 30 | 1995 | |
|
|
|||
| 5,347,654 System and method for optimizing and generating computer-based code in a parallel processing environment | 14 | 1992 | |
|
|
|||
| 2005/0091,025 Methods and systems for improved integrated circuit functional simulation | 10 | 2004 | |
Patent Citation Ranking
Maintenance Fees
| Fee | Large entity fee | small entity fee | micro entity fee | due date |
|---|---|---|---|---|
| 3.5 Year Payment | $1600.00 | $800.00 | $400.00 | Jan 27, 2014 |
| 7.5 Year Payment | $3600.00 | $1800.00 | $900.00 | Jan 27, 2018 |
| 11.5 Year Payment | $7400.00 | $3700.00 | $1850.00 | Jan 27, 2022 |
| Fee | Large entity fee | small entity fee | micro entity fee |
|---|---|---|---|
| Surcharge - 3.5 year - Late payment within 6 months | $160.00 | $80.00 | $40.00 |
| Surcharge - 7.5 year - Late payment within 6 months | $160.00 | $80.00 | $40.00 |
| Surcharge - 11.5 year - Late payment within 6 months | $160.00 | $80.00 | $40.00 |
| Surcharge after expiration - Late payment is unavoidable | $700.00 | $350.00 | $175.00 |
| Surcharge after expiration - Late payment is unintentional | $1,640.00 | $820.00 | $410.00 |