Items related to The Graph Isomorphism Algorithm: Graph Isomorphism...

The Graph Isomorphism Algorithm: Graph Isomorphism is in P - Softcover

Dharwadker, Ashay; Tevet, John-Tagore

 
9781466394377: The Graph Isomorphism Algorithm: Graph Isomorphism is in P
Softcover
ISBN 10: 1466394374 ISBN 13: 9781466394377
Publisher: CreateSpace Independent Publishing Platform, 2011

Synopsis

We present a new polynomial-time algorithm for determining whether two given graphs are isomorphic or not. We prove that the algorithm is necessary and sufficient for solving the Graph Isomorphism Problem in polynomial-time, thus showing that the Graph Isomorphism Problem is in P. The semiotic theory for the recognition of graph structure is used to define a canonical form of the sign matrix of a graph. We prove that the canonical form of the sign matrix is uniquely identifiable in polynomial-time for isomorphic graphs. The algorithm is demonstrated by solving the Graph Isomorphism Problem for many of the hardest known examples. We implement the algorithm in C++ and provide a demonstration program for Microsoft Windows.

"synopsis" may belong to another edition of this title.

Publisher
CreateSpace Independent Publishing Platform
Publication date
2011
Language
English
ISBN 10 
1466394374
ISBN 13 
9781466394377
Binding
Paperback
Number of pages
38