MathGroup Archive 2000

[Date Index] [Thread Index] [Author Index]

Search the Archive

graph isomorphism

  • To: mathgroup at
  • Subject: [mg21395] graph isomorphism
  • From: "Arturas Acus" <acus at>
  • Date: Mon, 3 Jan 2000 03:12:26 -0500 (EST)
  • Sender: owner-wri-mathgroup at

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

E-mail: acus at
   Fax: 370-2-225361
   Tel: 370-2-612906

  • Prev by Date: Problem with Rasters & Density Plots
  • Next by Date: Re: A better way to decimate a file??
  • Previous by thread: Re: Re: Problem with Rasters & Density Plots
  • Next by thread: Re: RE: Kronecker product of matrices