Back to Search Start Over

The BP Operator and Graph Isomorphism

Authors :
Randall Pruim
Uwe Schöning
Source :
Gems of Theoretical Computer Science ISBN: 9783642643521
Publication Year :
1998
Publisher :
Springer Berlin Heidelberg, 1998.

Abstract

The following results suggest that the Graph Isomorphism problem is not NP-complete, since, unlike the known NP-complete problems, Graph Isomorphism belongs to a class that can be defined by means of the BPoperator, an operator that has proven useful in many other applications as well.

Subjects

Subjects :
Combinatorics
Discrete mathematics
Computer science
Subgraph isomorphism problem
Voltage graph
Graph homomorphism
Induced subgraph isomorphism problem
Graph isomorphism
Graph property
Graph automorphism
Graph canonization

Details

ISBN :
978-3-642-64352-1
ISBNs :
9783642643521
Database :
OpenAIRE
Journal :
Gems of Theoretical Computer Science ISBN: 9783642643521
Accession number :
edsair.doi...........f43190ff2d288b718001e085d23accf1
Full Text :
https://doi.org/10.1007/978-3-642-60322-8_19
Full Text Access
View/download PDF

Tools

Authors Abstract Subjects Details