'Minimum cost to make connect all nodes in one partition of a weighted undirected bipartite graph

Given a weighted undirected bipartite graph between partition A and B, I'm trying to find the minimum cost to connect all nodes in partition A.

It seems like I need to first find a Minimum Spanning Tree (MST) of the whole graph and then exclude edges that are unnecessary (since I don't need to connect nodes in partition B). What I thought was to remove nodes in partition B with degree of 1 (only connected to 1 node in partition A) from the MST, but this method gave sub-optimal in some cases.

Hope somebody can help me on this.

Input format:

  • 1st line is N and M - size of partition A and B (1 < N, M < 1000)
  • Next is the cost matrix of size N x M. The value at row i and column j would be the cost to connect A[i] to B[j]

Output format:

  • The minimal cost to connect all nodes in A

Sample input:

3 4
1 2 3 7
1 3 1 2
3 4 1 7

Sample output:

4

Explanation:

  • Connect A[1] to B[1], A[2] to B[1], A[2] to B[3], and A[3] to B[3].This will connect all three nodes in A with the minimal cost of 4 in total.
algorithmgraphminimum-spanning-treebipartite


Solution 1:[1]

Partitions: A and B

Nodes: m and n (m,n < 1000)

We are trying to connect all nodes in A

Step 1: Create an exhaustive list of pairs of A-nodes, with min cost required to connect them. This will be (max) mC2 = m * (m-1) / 2 elements long list. For the example in the post, this will look like:

[(A1,A2,2), (A1,A3,4), (A2,A3,2)]

This is essentially a new graph with nodes only from A and respective edge weights. The easiest way to accomplish creating this is O(m^2 * n)

Step 2: This becomes your weighted graph for which you can apply MST logic to get to your final answer which will be O(m^2) solution (since number of edges ~m^2 >> number of nodes =m)

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1

Related Questions