,
Le problem est le suivant :
 
On as un graph compose de node et de liens. on veus couvrir tous le graph avec
des emiteurs wifi. Le but etant de minimiser les collisions.
Si une node A est lie a B, et une node C lie a B, si on mets un emiteur sur A et C
B recevra les deux emitions, donc colision.
 
Un petit diagram pour montrer ca

 
Le nombre de relays nest pas important le but est de minimiser les colisions.
   
Est ce un problem connu ? si oui quel est son nom que je puisse orienter mes recherche ?
 
un idee simple serait de parcourir tout le graph, On prend une node on lui attach emitter = true, et on garde une
liste des nodes qui sont couverte depuis cette node.on passe a la suivante, si elle est sur la liste des deja couverte  
on n y attache pas d emitter ect..
 
bon ca cest facile mais ca optimise rien du tout.

ne vous battez pas pour repondre

Avant de mettre un emitter à un sommet A, prendre la liste de tous ses sommets adjacents et vérifier pour chaque sommet X qu'il n'y a pas déjà un emitter adjacent à ce sommet X ?
 
Edit: ah oui le but est de couvrir tout le graphe   Ca a l'air assez particulier comme problème. M'enfin quelqu'un a peut etre une solution.

C'est un probleme de coloriage...

je pensais aussi, cest vrai que ca y ressemble mais le plus souvent els couleurs doivent etre differente entre chuaque node, or la cest pas tellement ca. comment traduire ce problem en utlisant les couleurs ?
 
sinon il  y aussi :
"weakly connected dominating sets for clustering ad hoc network"