Updating Directed Minimum Cost Spanning Trees

descriptionPublicationkeyboard_double_arrow_right Part of book or chapter of book , Conference object , Other literature type , Article 01 Jan 2006 Greece Publisher:Springer Berlin Heidelberg

Authors: Pollatos, G.G.; Telelis, O.A.; Zissimopoulos, V.;

doi: 10.1007/11764298_27

Updating Directed Minimum Cost Spanning Trees

- Summary
- Metrics

Abstract

We consider the problem of updating a directed minimum cost spanning tree (DMST), when edges are deleted from or inserted to a weighted directed graph. This problem apart from being a classic for directed graphs, is to the best of our knowledge a wide open aspect for the field of dynamic graph algorithms. Our contributions include results on the hardness of updates, a dynamic algorithm for updating a DMST, and detailed experimental analysis of the proposed algorithm exhibiting a speedup factor of at least 2 in comparison with the static practice.

Country

Greece

Related Organizations

National and Kapodistrian University of Athens
Greece

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	2
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average