A parallel algorithm for labeled graph isomorphism

被引：0

作者：

Abdulrahim, M ^{[1
]}

Misra, M ^{[1
]}

机构：

[1] Colorado Sch Mines, Dept Math & Comp Sci, Golden, CO 80401 USA

来源：

INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS, VOLS I-IV, PROCEEDINGS | 1998年

关键词：

parallel graph isomorphism; pattern recognition; graph matching; labeled graphs;

D O I：

暂无

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present a parallel algorithm to efficiently solve the graph isomorphism problem for most kinds of practical graphs. In many pattern recognition applications, patterns stored in a database may be represented by labeled graphs. Recognition of an input is achieved by comparing it to each stored graph. Our algorithm consists of three phases: preprocessing, link construction, and ambiguity resolution, and has a sequential time complexity of O(dn(6)log dn). We demonstrate the efficiency of the algorithm through an implementation on a shared memory MIMD machine.

引用

页码：1373 / 1380

页数：8