Dado un grafo y el número de grupos en los que queremos dividir el grafo, encuentra la mejor manera de dividir el grafo de modo que el diámetro máximo de todos los grupos sea mínimo
El grafo es no dirigido, el número de nodos en cada grupo (o sub-grafo) no necesariamente tiene que ser el mismo.
Esto es NP-completo, por reducción del problema de cobertura de cliques: los grafos de diámetro 1 son cliques, y decidir si hay una partición de un grafo dado en $k$ cliques es NP-completo.
Si en lugar de diámetro estuvieras buscando el radio, sería NP-completo por reducción del problema del conjunto dominante (donde el radio = 1).
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
