I'm studying mesh partitioning and I have the following problem. Suppose that I have a connected graph $$G$$ and an initial partition vector $$P$$, where $$P_i$$ indicates if the node $$i$$ belongs to subdomain 0 or 1. I need to smooth this partition configuration such that all subdomains are contiguos, which means that there is a path between each element of the same subdomain.
I tried to perform an smoothing using Fiduccia-Mattheyses and Kernighan-Lin, however these algorithms does not guarantee connected domains and the second one is not linear, it is an important constraint in my problem. I need some ideas about how to solve it.