Seite 1 von 1

Progress on Harmonious Tree subproject

Verfasst: 13.03.2012 14:00
von fwjmath
Harmonious Tree subproject has been running rather smoothly for a couple of months. Thanks everyone who have contributed to this subproject. Now I would take this oppotunity to report our progress on the verification.

Firstly some progress. We have cleared n=32,33,34, and results show that every tree with at most 34 nodes are harmonious, that is to say, the harmonious tree conjecture is correct up to 34 nodes. This extends the current result on n=31.

The verification for n=35,36 is running smoothly right now. You might see that some workunits do not seem to progress on your machine. But in fact they do.

There are two kinds of workunits, one is "fresh", the other is "recycled". Originally, trees are bundled up into fresh workunits using a method, which is computationally efficient, but generates bundles of different sizes. We then send out the fresh workunits. Since they differ in size, they might or might not be totally finished. For those not totally finished, we will generate a "recycled" workunit to continue the computation on the corresponding bundle. Sometimes we need to recycle several times for the same bundle.

For fresh workunits, the progress bar works rather well in most cases. For recycled workunits, in a good portion of the case, the progress bar will stay 0 (or blocked at some point) for a long time. This is due to the difficulty (or the size) of the bundle. If a bundle is recycled at least once, it is generally harder than the one-pass fresh ones. But even if the progress bar stays 0, if the computation done on the machine exceeds a certain limit, the application will finish and return partial result, so your machine will not be like stuck for a long time. Generally, it take 24-48 hours for your machine to reach this limit, that is to say, after 24-48 hours of computation, a workunit will be finished. So if you get a workunit labelled with an _R_, please finish it.

One more thing to report. In the verification of n=36, i.e. trees with 36 nodes, two "nearly-counter-examples" are discovered. Appearently the current application cannot find a harmonious labelling for them within the internal time limit. However, by throwing more computing cycles into them, harmonious labellings for them are found. In the end, they are still harmonious and not counter-examples, but only much more difficult than other trees for the currently used algorithm.

Thank you crunchers for all this contribution, and let's carry on the good work!

Re: Progress on Harmonious Tree subproject

Verfasst: 13.03.2012 21:43
von yoyo
Thank you for the update.
yoyo

Re: Progress on Harmonious Tree subproject

Verfasst: 14.03.2012 22:27
von Norman
:good: :good: :good: