From b4046f675f2cf97c9136f632a3f1898d9c08ec99 Mon Sep 17 00:00:00 2001 From: Alex AUVOLAT Date: Sun, 8 Dec 2013 19:40:17 +0100 Subject: Rien --- TODO | 22 ---------------------- algos.c | 2 -- media/2013-12-08-190058_1366x768_scrot.png | Bin 0 -> 232168 bytes 3 files changed, 24 deletions(-) delete mode 100644 TODO create mode 100644 media/2013-12-08-190058_1366x768_scrot.png diff --git a/TODO b/TODO deleted file mode 100644 index 4ec1f96..0000000 --- a/TODO +++ /dev/null @@ -1,22 +0,0 @@ -dichotomie? - -Coloriage : - - (On a toujours |K| + |C| > |K_max|, sinon ça sert à rien) - - Lorsque |C| = 10 (par exemple) et |K| < |K_max|, faire un coloriage du - graphe induit par C (ça se fait rapidement... mais ne pas le faire de - manière exacte). Si on a |K| + nb_couleurs <= |K_max|, alors on a perdu - (42). - -Utiliser des bitsets plus simples : - - Faire un typedef bitset_descriptor *set; On peut s'arranger pour faire, lors - de la création d'un bitset, *un seul malloc*, dont la première partie est - utilisée pour le descripteur et la seconde pour le tableau de bits. - -Analyse des cache miss ? - - - - diff --git a/algos.c b/algos.c index fdf7243..95fd1aa 100644 --- a/algos.c +++ b/algos.c @@ -9,8 +9,6 @@ * Trouve un coloriage non-optimal (mais parfois proche) du sous-graphe engendré * par s dans le graphe g. * Ne donne pas le coloriage, mais juste le nombre de couleurs d'un coloriage possible (nombre que l'on cherche à minimiser) - * Cet algorithme est assez naif mais il est fait pour tourner sur des graphes de taille petite (de l'ordre de 20), donc un - * algorithme même en n^3 ou n^4 est acceptable (ou pas...) */ void color_subgraph_aux(const graph g, int *colors, int *v, int *nneigh, const int n) { diff --git a/media/2013-12-08-190058_1366x768_scrot.png b/media/2013-12-08-190058_1366x768_scrot.png new file mode 100644 index 0000000..6696b38 Binary files /dev/null and b/media/2013-12-08-190058_1366x768_scrot.png differ -- cgit v1.2.3