Balanced Connected Partitioning of Unweighted Grid Graphs
Cédric Berenger, Peter Niebert, Kévin Perrot · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2018
We consider a partitioning problem for grid graphs with special constraints: a (square) grid graph as well as a number of colors is given, a solution is a coloring approximatively assigning the same number of vertices to each color and such that the induced subgraph for each color is connected. In a "rooted" variant, a vertex to be included in the coloring for each color is specified as well. This problem has a concrete motivation in multimedia streaming applications. We show that the general problem is NP-complete. On the other hand, we define a reasonable easy subclass of grid graphs for which solutions always exist and can be computed by a greedy algorithm.