27 Apr 2000 10:47:33 -0400

Related articles |
---|

On CFL equivalence and graph isomorphism johnston.p@worldnet.att.net (Paul Johnston) (2000-04-20) |

Re: On CFL equivalence and graph isomorphism lex@cc.gatech.edu (2000-04-25) |

Re: On CFL equivalence and graph isomorphism colohan+@cs.cmu.edu (Christopher Brian Colohan) (2000-04-25) |

Re: On CFL equivalence and graph isomorphism pmoisset@altavista.net (Pablo) (2000-04-25) |

Re: On CFL equivalence and graph isomorphism ger@informatik.uni-bremen.de (George Russell) (2000-04-26) |

Re: On CFL equivalence and graph isomorphism bdm@cs.anu.edu.au (2000-04-26) |

Re: On CFL equivalence and graph isomorphism dmolnar@fas.harvard.edu (David A Molnar) (2000-04-27) |

Re: On CFL equivalence and graph isomorphism miyazaki@symbolix.cs.uoregon.edu (2000-04-27) |

From: | miyazaki@symbolix.cs.uoregon.edu (Takunari Miyazaki) |

Newsgroups: | comp.theory,comp.compilers |

Followup-To: | comp.theory,comp.compilers |

Date: | 27 Apr 2000 10:47:33 -0400 |

Organization: | University of Oregon Computer Science Department |

Distribution: | inet |

References: | 00-04-140 00-04-167 00-04-184 |

Keywords: | theory |

Brendan McKay (bdm@cs.anu.edu.au) wrote:

*: Graph isomorphism is not known to be NP-complete, nor to be in P. It*

*: might turn out to be neither.*

As Professor McKay said, the graph-isomorphism problem is not known to

be in P nor NP-complete.

Certain complexity-theoretic evidence suggests that it is unlikely to

be NP-complete (see, e.g., J. Koebler, U. Schoening, and J. Toran, The

graph isomorphism problem: its structural complexity, Birkhaeuser,

1993).

On the other hand, if the vertex degrees are bounded by a constant,

Luks's group-theoretic algorithm performs isomorphism testing in

polynomial time (see E. M. Luks, Isomorphism of graphs of bounded

valence can be tested in polynomial time, J. Comput. System Sci. 25

(1982), 42-65).

Similar group-theoretic methods also yield the

asymptotically-best-known algorithm for general isomorphism testing,

with exp(sqrt(cn log n)) time for n-vertex graphs, due to Babai,

Kantor, Luks, and Zemlyachenko.

Takunari Miyazaki

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.