Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2000
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2000

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

Search the Archive

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


  • 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