[MUD-Dev] What about minimal spanning trees? was: what do we want

[Hans-Henrik Staerfeldt]

On Thu, 24 Sep 1998, Ola Fosheim Gr=F8stad wrote:

> J C Lawrence wrote:

[...snip...]

> Are these issues on topic?  And what about minimal spanning trees,

Recently one of my friends finished his thesis on fully dynamic
algorithms of graphs, where he actually gives an 'easy' and FAST
algorithm for minimal spanning tree (forest) in the dynamic case,=20
where things change. There is also an article:=20

  J.Holm, K. de Lichtenberg, and M. Thorup. Poly-logarithmic
  deterministic fully-dynamic algorithms for connectivity,=20
  minimum spanning tree, 2-edge and bi-connectivity.=20
  In Proc. 30th Symp. on Theory of Computation, 1998

In short it shows how you can maintain a minimum spanning forest
in O(log(n)^4) time per update. (which is much better than
previous results. For those sceptics, the constants involved are
not very large at that, and i imagine that it would be beneficial
to use in MUD's. (They also support connectivity dynamically in=20
O(log(n)^2) time).

Ofcause the article is just a description of the algorithm, you'd=20
still need to code it. But as these kinds of algorithms go its=20
EASY by comparison.

(is this on topic?)

Hans Henrik St=E6rfeldt         | =20
email: bombman at diku.dk        |  voice:      +45 40383492=20
  hhs at cbs.dtu.dk              |  voice work: +45 45252425
phone-mail:                   |  address:
  40383492 at sms.tdm.dk         |       Hans Henrik St=E6rfeldt,
WWW-home                      |       Dybendalsvej 74 2. th,
  http://www.cbs.dtu.dk/hhs/  |       2720 Vanl=F8se, Danmark.
                              |
Student of Computer Science   | Scientific programmer at Center for
  and Information Psychology. |   Biological Sequence Analysis,
  at University of Copenhagen |   Technical University of Denmark.