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