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

Check if an edge is contained in at least one MST
Автор mtkaya, история, 7 лет назад, По-английски

Hi, I have a question related to MST.

Suppose that we are given a graph where we have limited knowledge of the edge weights: Example

Is it possible to find all edges that are contained in at least one MST?

Thank you...

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

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

The problem statement is unclear. Are we to decide if an edge exists in a MST for all possible configurations of the question marks? Or if that edge exists in a MST for at least one possible configuration?

In either case it is possible to modify Kruskal's algorithm.

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

    Question mark means there is an edge but length of the edge is unknown!

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

      Well yeah, but in that case there are edges which might be in at least one MST if the unknowns have favorable valuables, but which might also not be in a MST. Should we include those edges?

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

        I guess we should not

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

          We will first find out whether each edge with a known weight definitely exists in some MST, then whether each edge with an unknown weight definitely exists in some MST. Both cases can be handled with a modified variant of Kruskal's algorithm.

          The worst case is when as many as possible edges with unknown values are in a MST. Let's make a DSU and add all the unknown edges to it. Now let's sort the edges with known weights by their weights and start processing the edges in blocks of equal weight. For each edge in a block, check if its endpoints are in different connectivity components (with the DSU), but don't merge them yet. If an edge's endpoints are in different connectivity components, the edge definitely exists in a MST. Once you've processed all the edges in a block, merge their endpoints in the DSU.

          Now for the edges with unknown weights. Make a new DSU and merge the endpoints of all edges with known weights. An edge with an unknown weight definitely exists in at least one MST if its endpoints are in different connectivity components in the DSU.

          The complexity of the first part is ; the complexity of the second part is , so the total complexity comes down to .

          → Ответить
  • »
    »
    7 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I believe what it means is that for each edge we need to determine if it's included in some MST, for any possible weights of the edges of the question marks.

    For that we could just immediately give all these edges a weight 0.

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

      Your comment is as ambiguous as the statement, but I see what you mean because of the weight 0 thing. Anyway we still need to consider when the edges with unknown weights are in any MST.

      → Ответить