ERA

No preview available

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3SX64C5K

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Computing Science, Department of

Collections

This file is in the following collections:

Technical Reports (Computing Science)

The Graph Isomorphism Problem Open Access

Descriptions

Author or creator
Fortin, Scott
Additional contributors
Subject/Keyword
graph isomorphism
Type of item
Report
Language
English
Place
Time
Description
Technical report TR96-20. The graph isomorphism problem can be easily stated: check to see if two graphs that look differently are actually the same. The problem occupies a rare position in the world of complexity theory, it is clearly in NP but is not known to be in P and it is not known to be NP-complete. Many sub-disciplines of mathematics, such as topology theory and group theory, can be brought to bear on the problem, and yet only for special classes of graphs have polynomial-time algorithms been discovered. Incongruently, this problem seems very easy in practice. It is almost always trivial to check two random graphs for isomorphism, and fast hardware implementations exist for application domains such as image processing. This paper is mostly a survey of related work in the graph isomorphism field. We examine the problem from many angles, mirroring the multi-faceted nature of the literature. We survey complexity results for the graph isomorphism problem, and discuss some of the classes of graphs which have known polynomial-time algorithms. Many of these algorithms have constants that are so large as to negate their usefulness in actual applications. Thus a number of practical techniques, which do not have a polynomial worst case, are also examined. We end the paper by discussing some graphs which are ``hard'' for practical algorithms, and present experimental results which demonstrate a class of graphs on which practical algorithms run into difficulty.
Date created
1996
DOI
doi:10.7939/R3SX64C5K
License information
Creative Commons Attribution 3.0 Unported
Rights

Citation for previous publication

Source
Link to related item

File Details

Date Uploaded
Date Modified
2014-04-24T23:04:28.911+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: postscript (Postscript)
Mime type: application/postscript
File size: 218871
Last modified: 2015:10:12 17:19:44-06:00
Filename: TR96-20.ps
Original checksum: adf11812ea0fc1cdaa72e7c641eb7b1a
Activity of users you follow
User Activity Date