Rechenkraft.net e.V.

Hi all,

I would like to propose something as a sub-project to yoyo@home. It is called Graceful Tree Verification, a manual volunteer computing project that aims to verify a notorious open problem (graceful tree conjecture) in graph theory.

This is its homepage: http://www.eleves.ens.fr/home/wfang/gtv/index_en.html. You can find all information on it.

About graceful labelling, please have a look at here or here.

I am the author of this little manual volunteer computing project. I am currently a master student in ENS Paris.

This project was started at the end of 2008. During its running, we had verified that every tree with no more than 35 nodes has at least a graceful labelling. This result beats the best record I can find on Google Scholar. However, due to limited programming experience, I had to distribute workunits manually. After I came up with a new algorithm, due to its nature, manual distribution of workunits quickly became so laborious that I had to pause the project to find a solution.

Would it be possible for yoyo@home to add my little project as sub-project? I have been thinking of "making it BOINC", so applications are written in a BOINC-compatible way (I think). It has its own checkpoint and also a progress bar (although not very accurate). It would not be very difficult to wrap it up with wrapper.

I am looking forward to any comment or reply.

fwjmath.

EDIT: please contact me via fwjmath(at)gmail.com

Hello,

I'm not an math expert. So I would enjoy to get some opinions of our math experts here.

yoyo

Hi,

for 'making it BOINC', a text-based client with an input- and an output-file would be the best thing to start with. From your description I assume the program has a GUI at the moment. What programming language is it written in? In order to be able to use your software with BOINC, you also need a program that can generate workunits, one that validates them and one that assimilates them into whatever format you desire your results to be in (e.g. a database).

I'm not a math expert either, but I understand the 'problem'. What I would like to know: is there a real-world application for this problem?

Best wishes for your project from Metz, FR ;)

mxplm hat geschrieben:Hi,

for 'making it BOINC', a text-based client with an input- and an output-file would be the best thing to start with. From your description I assume the program has a GUI at the moment. What programming language is it written in? In order to be able to use your software with BOINC, you also need a program that can generate workunits, one that validates them and one that assimilates them into whatever format you desire your results to be in (e.g. a database).

I'm not a math expert either, but I understand the 'problem'. What I would like to know: is there a real-world application for this problem?

Best wishes for your project from Metz, FR

Thanks for your reply!

In fact, the GUI is only for displaying information about current computation. The core application is indeed in a command-line style, written in C++, therefore also easily portable (I think). It reads an input file, writes to an output file (sometimes two), and checkpoints every now and then in a checkpoint file.

I have already a program to generate workunits, and validation is designed to be done by bitwise comparation of results. Assimilation is also easy, I just have to store all result files as backup, and eventually check for potential counter-examples that occur rarely.

Due to my work seperation algorithm, workunits may take different time to be done. For the matter of credit, I have an approximate estimation of work done in the final result file so that credit can be given according to actual work done to finish the workunit.

Graceful labelling can have real-world application. It can be apply to MPLS protocol.

Ayhan Basak, MPLS Multicasting Using Caterpillars and a Graceful Labelling Scheme, Eighth International Conference on Information Visualisation (IV?04), pp.382-387, 2004

In this paper, a caterpillar (this is a special kind of tree on which it is easy to find a graceful labelling) is used. But with this algorithm that calculates graceful labelling efficiently enough for arbitary tree (I hope), we might be able to extend this scheme to arbitary network topology by taking a spanning tree. This is one possibility. I am not an expert in network protocol, so I cannot say this for sure.

But of course, this project has more meaning to graph theory. It might happen that the graceful tree conjecture is false and we might find a counter-example of it in this search, though even for myself it is very unlikely to happen. It is so beautiful that it should be true. But so far, there is no demonstration of this conjecture, some experimental data might also be reassuring.

I will release the code soon on the project page, maybe tomorrow.

Good night,

fwjmath.

I have put my code on the project site:

http://www.eleves.ens.fr/home/wfang/gtv/apps/gtvb.cpp

It may be difficult to read, as I was lazy to put comments when writing it......

fwjmath.

fwjmath,
This seems to be very similar to a "Golomb Ruler" (a.k.a dnet's OGR ) but in a 2 dimensional arrangement and using sequential numbering instead of unique numbering.

would that be reasonably accurate description?

also
are you able to guess an estimate to the expected runtime for the entire next phase which would be n=36 yes?
ie based on your reference "Intel Core 2 Duo" machine.. how may days/months/years for a single machine? (so we can exprapolate based on estimate participation)


generally it sounds like a reasonable project.

shoelace hat geschrieben:fwjmath,
This seems to be very similar to a "Golomb Ruler" (a.k.a dnet's OGR ) but in a 2 dimensional arrangement and using sequential numbering instead of unique numbering.

would that be reasonably accurate description?

also
are you able to guess an estimate to the expected runtime for the entire next phase which would be n=36 yes?
ie based on your reference "Intel Core 2 Duo" machine.. how may days/months/years for a single machine? (so we can exprapolate based on estimate participation)


generally it sounds like a reasonable project.

Yes, your description is a good one. Graceful labelling is just like Golomb Ruler on trees, with a restriction on the range of labels.

Approximatively, when n increase by 1, the total computing time is multiplied by 3.09. As for n=35 it took 7.7 CPU year, n=36 will probably take something like 23.8*2/1.7=28 CPU year, 2 for double checking (necessary for the new algorithm), 1.7 for the better performance of the new algorithm. I say "something like" because for how much the new algorithm outperforms the old one is unknown for large n, but it seems to be more than a constant factor of 1.7.

For larger n, we can estimate the computation time roughly by the rule of thumb mentioned above: when n increase by 1, the total computing time is multiplied by 3.09.

I do benchmark on my own laptop, that is why everything is measured with a Core 2 Duo......

Thanks for your reply.

fwjmath.

I would be willing to crunch this as a Yoyo subproject subject to two conditions:

• Checkpointing in accordance with the interval set for the BOINC client, and
  Credit award on a rational scale consistent with other subprojects.

jjwhalen hat geschrieben:I would be willing to crunch this as a Yoyo subproject subject to two conditions:

• Checkpointing in accordance with the interval set for the BOINC client, and
  Credit award on a rational scale consistent with other subprojects.

For checkpointing, the application has a built-in checkpoint according to work done. It is about once every 2-5 minutes.

I cannot say much about credit scale, as it is to be decided by yoyo and other admins.

Thanks for your reply.

fwjmath.

I would love to tackle this new sub project.

Let's get to it already......

Regards,
Gentilli.

Hi everyone,

Any news yet on "Graceful Tree Verification" sub project?

Can't wait to start.......

Cheers,
Gentilli.

Hi fwjmath,

over the next months I'm trying to convert your gtvb.cpp into a proper BOINC executable. Could you please send me some sample input and output files, your compiler commands (for linking and building) and your functions to validate the results?

This is no official acceptance as a subproject, just my own interest in programming BOINC executables.

Regards
Christian