Frequency Allocation by Graph Coloring
This is a work I’ve done for the competitive entrance to the French grandes écoles during my second year in classes préparatoires aux grandes écoles (CPGE), as part of the travail d’initiative personnelle encadré test (commonly called TIPE). I was very young and this work is a bit old, but it may be worth take a look.
The general purpose of this work was to study methods for coloring graphs with approximated of exacts methods, with a focus on triangulated graphs. The concrete exemple of frequency allocation served as an excuse for coloring graph with arbitrary topology, as well as a particular class of graphs.
I’ve submitted a pretty report for the entrance exam to the ÉNS, which you can browse faithfully. That was my first try using LaTeX, so please be lenient. A fair more complete and detailed paper can be found here — but be aware that it was done in an ugly way using Word. I atone for my sins and use LaTeX henceforth. I’ve implementated the algorithms describes in this work and tested them of my computer. You can download the whole source code and use it at you convenience. Be careful : it is written is Caml Light, not Objective Caml (have I told you how I was young at this time ?). Finally there is also some slides I’ve made for the oral examinations, along with some extras.