ainta's blog

Offline Algorithm for dynamic MST
By ainta, 10 years ago, In English

I found a problem about dynamic MST.

To solve it, I read this paper.

But I cannot understand it(Is it divide-and-conquer?)

Please help me plz T.T

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

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

At first you can try to solve it by sqrt-decomposition:

1) Divide all queries to sqrt(max(n,m,k)) blocks.

2) In each block firstly add all edges that will be modified in block (denote it S) to mst in any order, and then try to add edges not from S one by one in non decreasing order to mst. If edge not from mst will be added then it should be in any mst in block, so you can merge the ends of that edge and make the number of vertexes equal to O(blockSize).

3) Now you should try to add edges not from S in non decreasing order to mst. Then each edge that will not be added to mst can't be in mst in block. So you can remove that edges and make number of edges equal to O(blockSize).

4) Finally you can simply build mst for each query in O(blockSize * alpha) time.

Okay. To get faster solution let's do the same in divide and conquer manner over queries: every time when we entering our solve function we should make the size of graph equal to the number of queries that we should process in function. So we have solution with complexity O(n * log^2n), cause we should sort the edges in block. Actually it's difficult to get complexity O(n logn) (I've not can) cause in paper authors telling us that we should firstly change all edges length by their numbers in sorted list of all lengths and then sort edges with integral lengths in O(numberOfEdges) time, but in that case we will get the constant about 16 or 32, cause the length of array will be different each time from (1 to n).

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

Is it possible to solve this question online? Like for example, using a link-cut? Thanks.

[Edit]: I realised the link to the problem above isn't working so, here's a rough outline of the qn.

So u have a graph with some edges. Then there are some queries, after each query an edge weight changes, and u are supposed to output the cost of the current mst. (the change continues from that query onwards, (not just within that single query))

U can submit here but problem statement is in chinese (https://www.lydsy.com/JudgeOnline/problem.php?id=2001)

This problem is offline, and can be solved with the method mentioned above, but I'm just wondering if an online solution exists. :)

→ Reply