I\'ve been looking for an algorithm which divides an undirected, weighted, plana

Question

I've been looking for an algorithm which divides an undirected, weighted, planar and simple graph into k disjoint subgraphs. Here, the graph is sparse, k is fixed, and there are no negative edge weights. After cutting, each subgraph must be connected (i.e. there must be a path between any two vertices of the subgraph which is only composed of vertices in that subgraph).

However, unlike most existing work on graph partitioning out there, I don't intend to obtain subgraphs that contain the same approximate number of vertices. Instead, I would like these subgraphs to have similar sum of edge weights. In other words, I would like to minimize the sum of edge weights of the subgraph with maximal weight and ideally cut long (weighted) edges.

Is there a name for this problem? I wasn't able to find anything about this on the web. Also, how can I approach this problem?

Explanation / Answer

If the graph is sparse, may be it's also bounded tree width. Then we can find the optimum cut by using dynamic programming for graphs of bounded treewidth1. To check whether it's a bounded tree-width or not there are some tools and you can use them. On the other hand, one (may be good) heuristic approach is finding maximum spanning tree. This can be done by negating edge weights and running Kruskal algorithm to find MST. Because the graph is sparse then heaviest cuts along this tree are not bad, also good cut for tree can be found by bottom up dynamic programming approach. (I think it's in factor of at most 5 with high probability in most cases).

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.