@Override
	public void run() {
		// TreeMap to store Prim's results ordered by their weight.
		// TODO: Try a minimum heap with min() in O(1) instead of a
		//       balanced tree (O(logn)).
		Map<Integer, Integer> roots = new TreeMap<Integer, Integer>();
		
		Edge[] edges = new Edge[this.edges.length];
		int n, weight, relevantEdges, root, lowerBound = 0;
	
		// Sort edges by weight.
		quickSort(0, this.edges.length - 1);
	
		// Compute initial lower bound (best k - 1 edges).
		// Choosing the cheapest k - 1 edges is not very intelligent. There is no guarantee
		// that this subset of edges even induces a subgraph over the initial graph.
		// TODO: Find a better initial lower bound.
		for (int i = 0; i < solution.length; i++) {
			lowerBound += this.edges[i].weight;
		}
	
		// Iterate over all nodes in the graph and run Prim's algorithm
		// until k - 1 edges are fixed.
		// As all induced subgraphs have k nodes and are connected according to Prim, they
		// are candidate solutions and thus submitted.
		for (root = 0; root < taken.length; root++) {
			taken = new boolean[taken.length];
			System.arraycopy(this.edges, 0, edges, 0, this.edges.length);

			taken[root] = true;
			n = 0;
			weight = 0;
			relevantEdges = this.edges.length;

			while (n < solution.length) { 
				for (int i = 0; i < relevantEdges; i++) {
					// XOR to check if connected and no circle.
					if (taken[edges[i].node1] ^ taken[edges[i].node2]) {
						taken[taken[edges[i].node1] ? edges[i].node2 : edges[i].node1] = true;
						solution[n++] = edges[i];
						weight += edges[i].weight;
						System.arraycopy(edges, i + 1, edges, i, --relevantEdges - i);
						break;
					}
					// Check for circle.
					else if (taken[edges[i].node1]) {
						System.arraycopy(edges, i + 1, edges, i, --relevantEdges - i);
						break;
					}
				}
			}
			// Sum up what we've just collected and submit this
			// solution to the framework.
			HashSet<Edge> set = new HashSet<Edge>(solution.length);
			for (int i = 0; i < solution.length; i++) {
				set.add(solution[i]);
			}
			setSolution(weight, set);
			roots.put(weight, root);
		}

		// Now for the real business, let's do some Branch-and-Bound. Roots of "k Prim Spanning Trees"
		// are enumerated by weight to increase our chances to obtain the kMST earlier.
		for (int item : roots.values()) {
			taken = new boolean[taken.length];
			System.arraycopy(this.edges, 0, edges, 0, this.edges.length);
			taken[item] = true;
			branchAndBound(edges, solution.length, 0, lowerBound);
		}
	}