He estado golpeando mi cabeza tratando de resolver el siguiente problema durante los últimos dos días, es una pregunta de la revisión en la preparación de mi examen, y yo supongo que algo similar va a estar en ella. El problema dice:
Encontrar el mínimo árbol de expansión de un grafo con |V|=n y |E|=n+k para alguna constante k tal que n>>k (modo gráfico es bastante escasa) en n+k^100 tiempo de ejecución (el k^100 en este caso es una función arbitraria). Cada una comparación de los costos de 1 unidad de tiempo (y por lo que tengo que reducir el número de comparaciones). La siguiente sugerencia fue dado: hoja de nodos (nodos de 1 grado) no tiene que compararse con los demás.
Mi idea original era usar algún tipo de Boruvka del algoritmo ya que se puede realizar de forma lineal en el número de aristas (si algunos de los bordes pueden ser eliminados en cada iteración). Me encantaría saber en qué dirección ir con este problema o si me falta algo que es obvio en este.
