graph isomorphism
- To: mathgroup at smc.vnet.net
- Subject: [mg21395] graph isomorphism
- From: "Arturas Acus" <acus at itpa.lt>
- Date: Mon, 3 Jan 2000 03:12:26 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
Dear Group,
recently I lacked a function in "Combinatorica" package
that could decide if two given graphs are isomorphics.
After some attempts I found an abstract in recent
scientific paper by Lin Chen "Graph isomorphism and
identification matrices: sequential algorithms"
in "Journal of computer and system sciences",
December 1999.
It is claimed in the paper
abstrct that the graph isomorphism problem
is "a famous open problem".
I know that this problem do not meet purposes of
the group, but sometimes similar
questions (especially in
ccombinatoric) are answered. So probably somebody
can advice me where to find more information
about the problem. At least, is it proved that
this problem is NP complete?
Unfortunately the article is not avialable
for me.
Thanks in advice
Dr. Arturas Acus
Institute of Theoretical
Physics and Astronomy
Gostauto 12, 2600,Vilnius
Lithuania
E-mail: acus at itpa.lt
Fax: 370-2-225361
Tel: 370-2-612906