Re: How to design a linear algorithm to determine whether two uncyclic graphs are ismophic
From: Richard Harter (cri_at_tiac.net)
Date: 01/21/05
- Next message: Rightleftright: "Re: Some simple math questions"
- Previous message: jstevh_at_msn.com: "Re: Surrogate factoring approach, analysis"
- In reply to: Joe: "How to design a linear algorithm to determine whether two uncyclic graphs are ismophic"
- Messages sorted by: [ date ] [ thread ]
Date: Fri, 21 Jan 2005 22:46:22 GMT
On 21 Jan 2005 08:42:29 -0800, Joe.ntang@gmail.com (Joe) wrote:
>Hi,
>
>Who can give me some advice on how to efficiently design an algorithm
>to judge whether two unicyclic graphs are ismophic.
If you are talking about graphs with undirected edges then a unicyclic
graph has to have a cycle with trees rooted in the cycle. So, prune
the leaves in each graph to get the cycle. This is O(n). Check that
the cycle lengths match. This is O(n). The tricky part is to
determine whether the trees are isomorphic. My impression is that the
obvious is O(n) but I haven't proved it to myself. An efficient
procedure is to create a signature for each tree such that two trees
are isomorphic if they have the same signature. The method for doing
this is left as an exercise for the student.
Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
All my life I wanted to be someone;
I guess I should have been more specific.
- Next message: Rightleftright: "Re: Some simple math questions"
- Previous message: jstevh_at_msn.com: "Re: Surrogate factoring approach, analysis"
- In reply to: Joe: "How to design a linear algorithm to determine whether two uncyclic graphs are ismophic"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
