 | | From: | Joe | | Subject: | How to design a linear algorithm to determine whether two uncyclic graphs are ismophic | | Date: | 21 Jan 2005 08:42:29 -0800 |
|
|
 | Hi,
Who can give me some advice on how to efficiently design an algorithm
to judge whether two unicyclic graphs are ismophic.
Thanks
|
|
| | From: | korax1214 at mailandnews.co.uk | | Subject: | Re: How to design a linear algorithm to determine whether two uncyclic graphs are ismophic | | Date: | 21 Jan 2005 14:12:36 -0800 |
|
|
| Joe wrote:
> Who can give me some advice on how to efficiently design an algorithm
> to judge whether two unicyclic graphs are ismophic.
In my experience, you're wasting your time posting an algorithm
question to sci.math; questions in algorithms, or indeed applied
mathematics generally, seem to be beyond the denizens of that group
(nobody there was even smart enough to answer a comparatively simple
question about regression analysis).
If you don't get the answer you want from comp.theory, try another
comp.* group (or perhaps alt.math).
(In the meantime, I'd still like to find out how to do *quadratic*
regression analysis...)
|
|
| | From: | Richard Harter | | Subject: | Re: How to design a linear algorithm to determine whether two uncyclic graphs are ismophic | | 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.
|
|
