140  Bandwidth
Moderator: Board moderators

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
Well, the first thing to do is to go down to O(8^2) by renaming the nodes to A,B,C,... consecutively. Then, you can gain some speedup if you build the permutations recursively and while building them already partly calculate the bandwith. Of course this also works in the iterative version, but only if you do it yourself rather than to rely on next_permutation of the STL.
If you want it really fast, you should have a look at the programs Skiena mentions in his book. Reportedly you can solve cases with 30 nodes in about a second or a minute, I don't remember.
If you want it really fast, you should have a look at the programs Skiena mentions in his book. Reportedly you can solve cases with 30 nodes in about a second or a minute, I don't remember.

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
Yes, that's the one I meant. You can get a small part of it here:
http://www.cs.sunysb.edu/~algorith/file ... idth.shtml
You can also find two implementations of solutions there, I believe from his students. And at least one of them contains a little documentation of the used algorithm somewhere.
http://www.cs.sunysb.edu/~algorith/file ... idth.shtml
You can also find two implementations of solutions there, I believe from his students. And at least one of them contains a little documentation of the used algorithm somewhere.

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut
140  bandwith
is sample output for problem 140 correct? or just only to show the right output format? i was curios since (correspond to sample input) node F is not adjacent of node C, but the sample output gives F after C.
thank you very much.
thank you very much.

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut
140  Bandwidth
I had no luck on this one so far... first problem I seem to stumble on.
What would be a good approach?
Googling lead me to consider some "cuthillmckee" algorithm, but I haven't been able to find a description of that algorithm online. Does anyone have such a description ?
Also, I'm not sure if the algorithm can easily find the lexicographically smallest solution.
So, at this stage, I would really be thankful for any links to some reference and/or hints towards a working approach.
TIA!  Ivan
What would be a good approach?
Googling lead me to consider some "cuthillmckee" algorithm, but I haven't been able to find a description of that algorithm online. Does anyone have such a description ?
Also, I'm not sure if the algorithm can easily find the lexicographically smallest solution.
So, at this stage, I would really be thankful for any links to some reference and/or hints towards a working approach.
TIA!  Ivan

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
140
Can anyone help me with this problem?
thx for any hints
thx for any hints