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

Graph with minimum bandwidth and at most k connected components
Автор govind53, история, 3 месяца назад, По-английски

There is a network graph given, in which we need to remove few edges to form at the most k connected components. Resulting graph should have minimum possible bandwidth (by bandwidth we mean maximum number of data packets which can pass through the graph). We need to identify the minimum bandwidth possible. Can someone please suggest possible approach to solve this problem?

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

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

You need to state the problem in more detail.

What do you mean by bandwidth? Pass through from where to where? Is it the same as maximum flow? Are the edges directed? Are source and sink given? If not, it's not clear at all how anything can pass through if there is more than one connected component.

Are there any bounds on the number of nodes in the network or $$$k$$$? What is the time limit? (Even if this is a problem from real life, not from a contest, you should have some realistic estimates.)

→ Ответить
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If I take what is in my mind the most obvious interpretation, then this problem will be pointless and weird:

    Given an undirected graph and two vertices $$$s$$$ and $$$t$$$. You may remove any number of edges. After the removal, the graph must not have more than $$$k$$$ connected components. Minimize the maximum flow between $$$s$$$ and $$$t$$$.

    I look at all the neighbors $$$u$$$ of $$$s$$$. If there is a path $$$u \leadsto t$$$ that doesn't visit $$$s$$$, I remove the edge $$$su$$$, otherwise I don't. In total, this increases the number of connected components by one, and now there is no path from $$$s$$$ to $$$t$$$ so the maximum flow is 0.

    If $$$k$$$ is equal to the initial number of connected components (i.e. I can't create a new one), I just don't delete one of the edges I would've deleted. Now the maximum flow is 1 and the number of connected components doesn't change.

    This doesn't feel like the intended problem, so I think something is still missing.

    → Ответить