CODEWITHSUNDEEP
algorithmgraph-theory
Rabie
Rabie

Reputation: 1

finding minimal subgraph in an undirected acyclic simple graph

I have an undirected acyclic simple graph with N nodes and N-1 edges (all nodes are connected to each others).

Removing the edge E_i splits the graph into exactly two sub-graphs having M_i and N-M_i nodes respectively.

I'm looking for an algorithm that searches the edges E_i to find the most equal partition of nodes: I want to find min(max(M_i, N-M_i)).

Upvotes: 0

Views: 375

Answers (2)

Prune
Prune

Reputation: 77860

I'll assume that the graph is represented by an edge list; from this we can create the corresponding list of nodes with their associated edges.

Rationale:

  • Consider each node to be its own cluster, weight 1.
  • Successively "merge" each leaf node into its parent, increasing the parent's weight.
  • At each iteration, build the lightest cluster available.
  • Continue until there are only two clusters remaining; the edge connecting them is the one to remove.

Initialize:

  1. Put all leaf nodes (order 1) into a list.
  2. Sort the list by increasing weight.
  3. Take the leaf node at the top of the list; merge it into its parent (add the weights).
  4. If the resulting node is now a leaf, insert the leaf at the appropriate point in the list.

Repeat steps 3 & 4 until there are only two nodes remaining; these form the desired partition.

Upvotes: 1

Mitsos101
Mitsos101

Reputation: 571

What is an undirected acyclic connected graph? That's right, a tree.

  1. Root the tree at an arbitrary vertex and calculate the size of each vertex's subtree.
  2. Let m(i) be the size of the i-th vertex's subtree.
  3. Let's assume you have fixed edge (u, v), with depth(u) < depth(v). Then, simply calculate max(m(v), N - m(v)).
  4. The minimum of all these values is your answer.

Upvotes: 2

Related Questions