A FAST BACKTRACK ALGORITHM FOR GRAPH ISOMORPHISM

被引：5

作者：

MITTAL, HB ^{[1
]}

机构：

[1] JAWAHARLAL NEHRU UNIV,SCH COMP & SYST SCI,NEW DELHI 110067,INDIA

来源：

INFORMATION PROCESSING LETTERS | 1988年 / 29卷 / 02期

关键词：

Mathematical Techniques--Graph Theory;

D O I：

10.1016/0020-0190(88)90037-3

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A backtrack algorithm is described to test two digraphs for isomorphism. Use is made of the degree sequence of vertices and a recursive procedure, using the distance matrices, to obtain the initial partitioning of vertices. The backtrack procedure maps vertices by composing rows and columns of the distance matrix. The algorithm is similar to that given by D.C. Schmidt and L.E. Druffel and is much faster than previously known algorithms.

引用

页码：105 / 110

页数：6

共 14 条

[1] BACKTRACK PROCEDURE FOR ISOMORPHISM OF DIRECTED GRAPHS [J].

BERZTISS, AT .

JOURNAL OF THE ACM, 1973, 20 (03) :365-377

[2] REFINED VERTEX CODES AND VERTEX PARTITIONING METHODOLOGY FOR GRAPH ISOMORPHISM TESTING [J].

BHAT, KVS .

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS, 1980, 10 (10) :610-615

[3] AN EFFICIENT ALGORITHM FOR GRAPH ISOMORPHISM [J].

CORNEIL, DG ;

GOTLIEB, CC .

JOURNAL OF THE ACM, 1970, 17 (01) :51-&

[4] A THEORETICAL-ANALYSIS OF VARIOUS HEURISTICS FOR THE GRAPH ISOMORPHISM-PROBLEM [J].

CORNEIL, DG ;

KIRKPATRICK, DG .

SIAM JOURNAL ON COMPUTING, 1980, 9 (02) :281-297

[5]

Deo N., 1977, BIT (Nordisk Tidskrift for Informationsbehandling), V17, P16, DOI 10.1007/BF01932396

[6] ALGORITHM-97 - SHORTEST PATH [J].

FLOYD, RW .

COMMUNICATIONS OF THE ACM, 1962, 5 (06) :345-345

[7] BACKTRACK PROGRAMMING [J].

GOLOMB, SW ;

BAUMERT, LD .

JOURNAL OF THE ACM, 1965, 12 (04) :516-&

[8] DISTANCE MATRIX OF A GRAPH AND ITS REALIZABILITY [J].

HAKIMI, SL ;

YAU, SS .

QUARTERLY OF APPLIED MATHEMATICS, 1965, 22 (04) :305-+

[9]

Harary F., 1972, GRAPH THEORY

[10]

Read R. C., 1977, J GRAPH THEOR, V1, P339, DOI DOI 10.1002/JGT.3190010410

← 1 2 →