A heuristic algorithm of recognition of isomorphism of graphs

被引：0

作者：

Glibovets N.N. ^{[1
]}

Ivashchenko S.A. ^{[1
]}

机构：

[1] National University Kievo-Mogilyanskaya Akademiya, Kiev

来源：

Cybernetics and Systems Analysis | 2001年 / 37卷 / 1期

关键词：

Graph isomorphism; Heuristic algorithm; Recognition of isomorphism of graphs;

D O I：

10.1023/A:1016632503967

中图分类号：

学科分类号：

摘要：

A heuristic polynomial algorithm is presented, which is used for the recognition of isomorphism of graphs and can be assigned to the group of methods that use local characteristic invariants of graphs. At each step, the behavior of the algorithm depends on information obtained at its previous steps. All the theorems stated are proved for a class of nonoriented graphs. © 2001 Kluwer Academic/Plenum Publishers.

引用

页码：138 / 143

页数：5

共 50 条

[1] A graph isomorphism algorithm for object recognition
M. A. Abdulrahim
M. Misra
Pattern Analysis and Applications, 1998, 1 : 189 - 201
[2] A graph isomorphism algorithm for object recognition
Abdulrahim, MA
Misra, M
PATTERN ANALYSIS AND APPLICATIONS, 1998, 1 (03) : 189 - 201
[3] AN ALGORITHM FOR OPTIMAL ISOMORPHISM BETWEEN 2 RANDOM GRAPHS
SEONG, DS
CHOI, YK
KIM, HS
PARK, KH
PATTERN RECOGNITION LETTERS, 1994, 15 (04) : 321 - 327
[4] A heuristic algorithm to find rupture degree in graphs
Durgut, Rafet
Turaci, Tufan
Kutucu, Hakan
TURKISH JOURNAL OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCES, 2019, 27 (05) : 3433 - 3441
[5] Accelarating graph isomorphism algorithm by finer classification of layered graphs
Fukuda, K
Nakamori, M
PDPTA'2001: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS, 2001, : 1271 - 1276
[6] A Correction to the Heuristic Algorithm MinimalFlipSet to Balance Unbalanced Graphs
Kundu, Sukhamay
Nanavati, Amit A.
COMPLEX NETWORKS & THEIR APPLICATIONS XII, VOL 3, COMPLEX NETWORKS 2023, 2024, 1143 : 134 - 146
[7] A LINEAR-TIME ALGORITHM FOR ISOMORPHISM OF GRAPHS OF BOUNDED AVERAGE GENUS
CHEN, JN
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1994, 7 (04) : 614 - 631
[8] FRACTIONAL ISOMORPHISM OF GRAPHS
RAMANA, MV
SCHEINERMAN, ER
ULLMAN, D
DISCRETE MATHEMATICS, 1994, 132 (1-3) : 247 - 265
[9] Network-on-chip heuristic mapping algorithm based on isomorphism elimination for NoC optimisation
Weng Xiaodong
Liu Yi
Yang Yintang
IET COMPUTERS AND DIGITAL TECHNIQUES, 2020, 14 (06) : 272 - 280
[10] A SIMPLE AND FAST HEURISTIC ALGORITHM FOR EDGE-COLORING OF GRAPHS
Fiol, M. A.
Vilaltella, J.
AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2013, 10 (03) : 263 - 272

← 1 2 3 4 5 →