en mots, quelqu'un peut-il afficher des directions vers la recherche de l'ensemble indépendant 'maximal' dans un graphe simple? J'ai lu quelque chose du site ETH qui dit qu'on peut trouver un tel dans O (n) en choisissant simplement un sommet aléatoire v et en scannant le reste et en essayant de trouver s'il y a un bord de v au reste.Algorithme pour trouver l'ensemble indépendant 'maximal' dans un graphe simple
Merci
Oui, par définition, un ensemble maximal est indépendant dont un ensemble indépendant auquel les sommets ne plus peuvent être ajoutés sans violer la condition de « l'indépendance ». Donc, simplement choisir des sommets jusqu'à ce que vous ne puissiez plus en choisir un ensemble indépendant maximal, peut être fait en temps linéaire (c'est-à-dire linéaire en | V | + | E |).
Notez que ceci est différent de maximum ensemble indépendant, qui est un ensemble indépendant de la plus grande taille possible et qui est NP-Hard.
trouvé sur le web, probablement d'une classe » Pour accompagner le texte` `Introduction à Parallel Computing '', Addison Wesley, 2003
Trouver un Maximal ensemble indépendant (MIS)
parallel MIS algorithms use randimization to gain
concurrency (Luby's algorithm for graph coloring).
Initially, each node is in the candidate set C. Each
node generates a (unique) random number and
communicates it to its neighbors.
If a nodes number exceeds that of all its neighbors, it
joins set I. All of its neighbors are removed from C.
This process continues until C is empty.
On average, this algorithm converges after O(log|V|)
such steps.
Mais c'est O (m^2), où m est la taille de l'ensemble indépendant que vous trouvez.Pour un graphique avec très peu d'arêtes, c'est près de O (n^2) – Artelius
Il est linéaire en nombre d'arêtes Dans les problèmes de graphes, la représentation importe et linéaire signifie habituellement | V | + | E |. Techniquement parlant, la taille de l'entrée pourrait être plus grande que | V | + | E |. Désolé si ce n'était pas clair. Je vais modifier la réponse. –
NP-Hard, cela signifie-t-il qu'il n'y a pas non plus de solution pseudo-P? –