Rui Xu:
Analysis of a Dynamic Minimum Spanning Tree Algorithm in a Planar Graph
Kurzbeschreibung
This thesis presents a comprehensive survey of methods for maintaining a dynamic Minimum Spanning Forest in planar graphs, with a focus on analyzing the approaches of Gabow and Stallmann, as well as the work of Eppstein et al. Gabow and Stallmann’s method provides optimal performance for edge weight modifications in fixed graph struc- tures, while Eppstein et al. extended this by introducing support for dynamic structural changes. Their approach is based on a dynamic tree data structure, which allows the algo- rithm to achieve logarithmic time complexity per operation and linear space complexity. Additionally, a discussion on the lower bounds of the algorithms’ time complexity confirms their optimality under certain computational models.