Блог пользователя TuHoangAnh

Автор TuHoangAnh, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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.