首页>
外国专利>
SYSTEM AND METHOD FOR IDENTIFYING MAXIMAL INDEPENDENT SETS IN PARALLEL
SYSTEM AND METHOD FOR IDENTIFYING MAXIMAL INDEPENDENT SETS IN PARALLEL
展开▼
机译:并行识别最大独立集的系统和方法
展开▼
页面导航
摘要
著录项
相似文献
摘要
A method for identifying maximal independent sets in parallel may include, on a processor, accessing data representing an undirected graph, generating a respective initial priority value for each vertex, dependent on the vertex degree and an average degree for vertices in the graph, and recording an indication of the initial priority value for each vertex. The method may include determining, for multiple vertices, that no neighbor vertex has a priority value that is higher than that of the vertex. In response, the method may include recording respective indications that each neighbor vertex connected is not to be included in a maximal independent set for the undirected graph and recording an indication that the vertex is to be included in the maximal independent set. The determinations and recordings may be performed in parallel by respective processing elements of the processor. The processor may be a GPU.
展开▼