pimenta's blog

Improve minimum spanning tree with new edge, with better running time than O(|V|)
By pimenta, 9 years ago, In English

The problem gives a MST T and a series of Q queries, each one with a new edge e = {u, v} such that no edge between u and v exists in T. For every query, we have to improve T with e and print the new weight of T.

The best I can do is run a DFS (O(|V|)) to find the current path P between u and v, and find the heaviest edge in P. If , we improve T removing and inserting e. The overall running time for a test case is O(Q|V|).

Does anybody know an asymptotically faster algorithm for this problem?

Thanks in advance!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I know, it's called link/cut tree. It can solve the problem in O(Qlog|V|) online (and many other tree-related problems). I wouldn't call it easy to understand or implement, though. Not even talking about proof of time boundary.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry, I don't understand. It's for the whole test case??? It's like , but Q is not important? Is that it?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, I get it. Each operation costs . It's actually for a test case. Thanks! Very helpful!

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yep, I'm sorry, fixed that.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I finally implemented the DS, but I'm having trouble to augment it to support the query I need. I need something like , the heaviest edge in the path from the root to u, and what vertices are incident to this edge. I'd appreciate any help!

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          You can take a look at these posts: original, follow-up (Russian only).

          Tl;dr: one possible way of doing something with edges is to add artificial vertices on the middle of every edge and use them instead of edges, remaining vertices can be filled with some "neutral" value (like  - ∞ in case of maximum) or just marked as "skip this vertex" (which is essentially the same).

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
            ← Rev. 4   Vote: I like it 0 Vote: I do not like it

            Thanks! Good idea! Now I'm debugging my code, and I found that my link() operation is not working correctly, because it requires that one of the vertices to be the root of its tree. Do you know how to implement this makeroot(v) operation, or any other workaround to this problem? Thanks again for the help!

            Edit: I saw that this makeroot(v) is actually called evert(v), but I can't find a good site/tutorial/code or whatever that I could understand... I saw the operation in Sleator's original paper, but I'm having too much trouble to understand...

            Edit2: Ok, evert is just swapping childs in a whole splay tree. My code is now correct, but slow... Probably because evert needs lazy propagation to run in O(lg n), right?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it -8 Vote: I do not like it

              Could you please provide a link to the code for the same?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                OMG I can't remember the problem, sorry =(

                → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I just want to point out that you are searching for a path in the MST, which itself has size of O(|V|), so the algorithm is actually O(Q * |V|) in total. I know it's not that significant but it was actually given as a problem in IOI long time ago, with the author solution being O(Q * |V|).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Indeed, trees have |E| = |V| - 1 = O(|V|)! But I was aware of that writing the post. I'll edit, thanks!

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Do the same thing as in LCA algorithm, but save not only 1, 2, 4, 8... parents, but also maximum among 1, 2, 4, 8 edges on the path to the root. Then you can answer a query in logN. No link-cut trees!

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    And how do we update the LCA DS, removing an edge and inserting a new one?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, I understand, you didn't point clearly that the tree changes after each query.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I pointed that in the first paragraph!

        → Reply