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.
I know
algorithm for that problem. Is it suitable?
What does this method look like?
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
Thanks this is what I want.
Will dynamic tree work in this problem to make O(N log N) online algo?