Treffer: Experimental Analysis of Algorithms for Updating Minimum Spanning Trees on Graphs Subject to Changes on Edge Weights.
Title:
Experimental Analysis of Algorithms for Updating Minimum Spanning Trees on Graphs Subject to Changes on Edge Weights.
Authors:
Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Rangan, C. Pandu, Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Demetrescu, Camil demetres@dis.uniroma1.it, Ribeiro, Celso C.1 celso@inf.puc-rio.br, Toso, Rodrigo F.1 rtoso@rutcor.rutgers.edu
Source:
Experimental Algorithms (9783540728443). 2007, p393-405. 13p.
Database:
Supplemental Index
Weitere Informationen
We consider the problem of maintaining a minimum spanning tree of a dynamically changing graph, subject to changes on edge weights. We propose an on-line fully-dynamic algorithm that runs in time O(<INNOPIPE>E<INNOPIPE>) when the easy-to-implement DRD-trees data structure for dynamic trees is used. Numerical experiments illustrate the efficiency of the approach. [ABSTRACT FROM AUTHOR]