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

ALSO PUBLISHED AS: 20060034194

Stats

ATTORNEY / AGENT: (SPONSORED)

Importance

Loading Importance Indicators... loading....

Abstract

See full text

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... loading....

First Claim

See full text

all claims..

Related Publications

Loading Related Publications... loading....

Patent Owner(s)

Patent OwnerAddressTotal Patents
CRAY INC.SEATTLE, WA219

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

Inventor Name Address # of filed Patents Total Citations
Kahan, Simon H Seattle, WA 12 124

Cited Art Landscape

Patent Info (Count) # Cites Year
 
AGILENT TECHNOLOGIES, INC. (1)
6,438,734 Fast search method for enabling a computer to find elementary loops in a graph 8 1997
 
AGILIX CORPORATION (1)
2002/0087,275 Visualization and manipulation of biomolecular relationships using graph operators 14 2001
 
APPLE INC. (1)
5,784,557 Method and apparatus for transforming an arbitrary topology collection of nodes into an acyclic directed graph 69 1996
 
BOARD OF SUPERVISORS OF LOUISIANA STATE UNIVERSITY AND AGRICULTURAL AND MECHANICAL COLLEGE (1)
6,442,663 Data collection and restoration for homogeneous or heterogeneous process migration 65 1998
 
CALIFORNIA INSTITUTE OF TECHNOLOGY (1)
5,170,393 Adaptive routing of messages in parallel and distributed processor systems 56 1990
 
CRAY INC. (1)
2006/0034,194 Identifying connected components of a graph in parallel 4 2005
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (1)
6,230,151 Parallel classification for data mining in a shared-memory multiprocessor system 35 1998
 
NOKIA SIEMENS NETWORKS GMBH & CO. KG (1)
5,732,072 Method for adaptive routing in a communication network 32 1995
 
TM PATENTS, L.P. (1)
5,347,654 System and method for optimizing and generating computer-based code in a parallel processing environment 14 1992
 
VENTURE LENDING & LEASING IV, INC. (1)
2005/0091,025 Methods and systems for improved integrated circuit functional simulation 22 2004

Patent Citation Ranking

Forward Cite Landscape

  • No Forward Cites to Display

Maintenance Fees

Fee Large entity fee small entity fee micro entity fee due date
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 - 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