Edvard's blog

Dynamic MST problem
By Edvard, 11 years ago, In English

Hi everyone!

Today I've got to know that there is a nice algorithm for online MST problem.

The problem looks like this: we have an undirected weighted graph and queries to change the weight of edge, after each query need to find the weight of MST.

I've heard that exist an O(n logn) algorithm for this problem. Can anyone give me some link to the article? Or any book in which I can read about it. Thanks in advance.

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

»
11 years ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

I know algorithm for that problem. Is it suitable?

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

http://acm.sgu.ru/problem.php?contest=0&problem=529

Are you talking about this problem?

If so there is an O(n log n) approach to touch it by an offline style(you read all update at the beginning, and solve the queries in one move).check this:http://www.dmi.unict.it/~faro/algocom/prova03/paper02.pdf

Otherwise There's is s an O(n^0.5) per update approach like this:http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1367&context=cstech

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

Will dynamic tree work in this problem to make O(N log N) online algo?

→ Reply