TuHoangAnh's blog

maximize the number of connected components in a graph.
By TuHoangAnh, history, 3 years ago, In English

given an undirected graph, you have to remove some nodes to maximize the number of connected components.

when removing a node, you have to remove all its edges.

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by TuHoangAnh (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

It's just the size of maximum independent set.

Proof: If the optimal set of remaining vertices doesn't form an independent set, simply take one vertex from each of the components.

→ Reply