Title

Attacks On Hard Instances Of Graph Isomorphism

Abstract

The Graph Isomorphism (GI) problem asks if two graphs are isomorphic. Algorithms which solve GI have applications in but not limited to, SAT solver engines, isomorph-free generation, combinatorial analysis, and analyzing chemical structures. However, no algorithm has been found which solves GI in polynomial time, implying that hard instances should exist. One of the most popular algorithms, implemented in the software package nauty, canonically labels a graph and outputs generators for its automorphism group. In this paper we present some methods that improve its performance on graphs that are known to pose difficulty.

Publication Date

2-1-2008

Publication Title

Journal of Combinatorial Mathematics and Combinatorial Computing

Volume

64

Number of Pages

203-225

Document Type

Article

Personal Identifier

scopus

Socpus ID

78651544306 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/78651544306

This document is currently not available here.

Share

COinS