# Finding optimal parallelization from general weighted undirected graph

I am solving a problem of "blending" sets of overlapping images. These sets can be represented by undirected weighted graph such as this one:

Each node represents an image. Overlapping images are connected by an edge. Edge weight represents overlap area size (blending larger overlap sooner leads to better overall quality).

The algorithm generally removes edges. It can do it sequentially or in parallel. However, when blending occurs, the nodes merge and the graph structure changes. So parallelization is possible only on connected components that are themselves not overlapping!

Such non-overlapping components are D-B and F-E-G. We can run the blending algorithm on these components safely in parallel. The result is the following graph (merged nodes are displayed in green):

Now there is no further parallelization possible because any two connected components are overlapping (they have an edge directly between them).

The parallel version of the algorithm would look like this:

1. Find connected components (no two are connected directly) and create task for each.
2. Run the tasks in parallel.
3. Update graph.
4. Until single node remains, continue with 1.


The tricky part is the first step: How to find best set of connected components?

One way would be a greedy algorithm that simply finds the largest number of components at a given iteration. The greedy algorithm will maximize parallelization in the beginning but at the cost of many iterations later.

The optimal solution may be bringing good amount of connected components in each iteration to maximize parallelization and minimize number of iterations at the same time (so there are two variables in the optimization).

I can't think of any optimization algorithm other than backtracking, i.e. search space of all possible evolutions and choose the one with maximum parallelization.

Edge weights can be ignored, but improved version of the algorithm may take it into account as larger areas takes more time to blend (e.g. area of size 200 will take roughly twice the time to blend than two areas of size 100). Taking weights into account may lead to better strategy on selecting components (faster overall running time of the algorithm).

Do you have any clues for such optimization algorithm, that finds the best strategy of selecting parts of graph so that there is maximum parallelization and minimum number of iterations?

• Connected component is not the right word here. The original graph is connected. Do you mean partition the vertices to $T,S_1,\ldots,S_k$, such that the distance between $S_i$ and $S_j$ is at least 2? There is no restriction on how $S_i$ should look like?(for example I don't see how you "blend" any subgraph). It's also unclear what you mean by iterations. – Chao Xu Dec 15 '13 at 21:22