Salut, je m'interesse au probleme du "dominating set", (la traduction  
"ensemble dominé" me semble pas super) j'ai compris que c'était un  
sous-ensemble de sommets (dans un graphe connexe supposons) qui avec leur
voisins directs constituent tous les sommets du graphe.  
 
J'ai essayé d'ecrire un algo avec une fonction qui genere a chaque  
appel un sous-ensemble de l'ensemble des sommets et un predicat qui teste
si ce sous-ensemble nous satisfait (en gros si on a un graphe  
G=(V,E) on veut V' inclus dans V tel que pour tout u € V => v € V' pour
lequel (u,v) soit une arete donc soit € E). Donc je pense dans le pire
des cas on doit se taper toutes les generation de sous-ensemble et là
on est dans du O(2^n) donc expo, pas bon.    
 
Malheureusement je n'arrive pas a trouver le critere "greedy"  
pour ce probleme, si bien sur il existe. Une aide serait la bienvenue
 
Bon je sais que c'est du NP-complet, donc pas facile, mais une autre
approximation est surement possible. (dans les trucs que j'ai trouvé en
anglais je pige pas grand chose) On sens que c'est pas loin du  
probleme de "vertex covering" sauf que la on veut les sommets
et pas les arcs.  
 
Et puis juste pour etre sur, il n'y a pas de "domintating set" pour
un graphe a 3 sommets et a 3 aretes ?  
 
           *
          / \
         *---*
 
(sinon ca voudrait dire que l'on peut avoir des sommets seuls dans V'?)

Y-t'il vraiment personne qui touche à l'optimisation combinatoire ?

dans un graphe complet, n'importe quel sommet pri separemment est un dominating set  
 
pour le reste , je seche

Ok, ca je suis daccord. Si le graph est complet c'est trivial. (pas possible, j'ai utilisé ce mot   )

Et mal employé : trivial ça veut dire vulgaire.

Bien entendu j'ai employé le mot trivial avec la signification de "evident" et non "vulgaire", désolé de t'avoir choqué matafan.

Pourtant employé dans ce contexte par les profs de math  

a priori c un pb np complet( un nombre exponentiel de as a étudier )  
donc dans le cas général , tu vas avoir du mal résoudre , a moins de rester sur de petits graphes , ou sur des graphes particuliers

"Dans un graphe simple G, un sous-ensemble D de sommets est un ensemble dominant total si tout élément de G a au moins un voisin dans D"
 
Donc je ne vois pas ou est le probleme avec le graphe complet a trois aretes.
 
hors sujet : trivial c'est employe par tous les profs de maths du secondaire...

Moi non plus. Chronoklazm, tu peux expliquer ?
 

Et aussi par des profs d'unif et du supérieur, hein. C'est peut-être un régionalisme.

 
A partir de là, tout est devenu clair et limpide pour moi (concernant le graphe complet a 3 sommets)
Donc oublions les graphes complets ou ca ne sert pratiquement a rien de chercher un dominated set
 
Mon probleme principal (comme je l'ai dis dans le tout premier post) est de
trouver un critere greedy pour realiser un algo abstrait.
 
Recapitulons..
 
On a la formalisation suivante :
 
I (input) : G=(V,E) (ou V est l'ensemble des sommets et E l'ensemble des arretes)
 
S (la solution) : { V' inclus ou egal dans V / Pour tout u € V-V' => v € V' pour lequel (u,v) € E }
 
f (fonction de mesure de la solution) : |V'| (cardinalité de V')
 
opt (critere d'optimisation) : MIN (on veux minimiser la solution)
 
En gros on veux trouver le plus petit sous-ensemble de V qu'on appele V' tel que V' soit un dominating set.
Grace a ce sous ensemble V' on pourras avoir tous les sommets du graphe, et de plus on pourras reconstituer le graphe original en tracant les "bonnes" arretes entre les sommets.  
 
Ca peux servir a plein de choses (cryptographie, optimisation des reseaux etc..), c'est un probleme "MODELE" comme le voyageur de commerce, le subset-sum etc
 
Ce probleme est NP-dur ! Donc officielement il n'existe pas d'algorithme polynomial (dit en P) pour ce probleme.
 
Voici un algorithme generique :
 
L = tableau d'apparition des sommets ou les indices sont les numero des sommets
c'est un tableau de booleens en gros ou 1 sera present et 0 sera absent.
 
list_adj(i) = renvoi la liste d'adjacence du sommet i.
 
nextSE(L) = renvoi le sous-ensemble suivant de L
 
----------------> DSGenerique(L)
 
1. P?(L)==vrai => DSGenerique(L) = L
2. P?(L)==faux => DSGenerique(L) = DSGenerique(nextSE(L))
 
----------------> P?(L) = Dom(L, i, n)  
 
1. (i<=n)&&(L[i]==1) => Dom(L, i ,n) = Dom(L, i+1, n)
2. (i<=n)&&(L[i]==0) => Dom(L, i ,n) = alpha(L, list_adj(i), n, i)
3. (i>n)             => Dom(L, i ,n) = vrai
 
---------------> alpha(L, x*M, i, n) ; x est premier element de la liste M  
 
1. L[x]==1           => alpha(L, x*M, i, n) = Dom(L, i+1, n)
2. L[x]==0           => alpha(L, x*M, i, n) = alpha(L, M, i, n)
3. M est vide        => alpha(L, x*M, i, n) = faux
 
---------------------------------------------------------------------------
 
Bon je ne vai pas faire la trace car ce serai trop long, en tout cas on se rend compte que
au pire des cas on doit executer tout ca 2^|L| fois pur tomber sur un sous-ensemble qui nous satisfait.
Donc la complexité (sans rentrer dans les details) est clairement expo ( O(2^k) c'est pas genial comme approximation ) !    
 
Donc mon probleme est de trouver une heuristique qui permetrait d'avoir une meilleure approximation, peut etre aussi expo mais dont l'algo serait un peu plus fut-fut que ca, car l'algorithme generique ne fait que "traduire" la solution.
On pourais peut etre jouer sur la degré des sommets...
 
Voilà le probleme

tu peux peut etre elaguer un peu ton probleme avec la recherche de sous graphes maximaux connexe ( sachant que les dominating set seront disjoint )  
la recherche de graphe connexe doit pouvoir se faire en  O(n) , en coloriant les noeuds par exemple

Flûte ça a l'air super intéressant mais là je dois vraiement aller dormir.

Bon, alors là je comprends pas comment tu as pu louper ça avec google : http://distcomp.ethz.ch/lectures/s [...] pter12.pdf
 
Il te parles de ton heuristic probabiliste que tu recherches. Dis-nous si c'est ce qu'il te fallait
 
edit : dsl, j'avais pas vu la date...