Solver MPIDS
Encuentra el Minimum Positive Influence Dominating Set en un grafo — el conjunto más pequeño de nodos donde cada vértice tiene al menos la mitad de sus vecinos en el conjunto. Elige un grafo de muestra o carga el tuyo, luego ejecuta búsqueda voraz (greedy) o local.
Encuentra el conjunto S más pequeño de nodos tal que cada vértice v tenga al menos ⌈deg(v)/2⌉ vecinos en S. Los nodos en el conjunto son morados, los nodos dominados son verdes, y los nodos no dominados son rojos.
Sobre este proyecto
Originalmente un proyecto en C++ para el curso de Algoritmia en la FIB-UPC, resolviendo el problema MPIDS con heurísticas voraces, simulated annealing e ILP con CPLEX. Esta demo de navegador es un port de los algoritmos de búsqueda voraz y local a TypeScript con una visualización interactiva de grafos dirigida por fuerzas.