Optimal MST maintenance for transient deletion of every node in planar graphs

摘要: Given a minimum spanning tree of 2-node connected, real weighted, planar graph G = (V, E) with n nodes, we study the problem finding, for every node v ∈ V, - (the deprived and all its incident edges). We show that this can be solved on pointer machine in optimal linear time, thus improving previous known O(n ċ α(n, n)) time bound holding general sparse graphs, where α is functional inverse Ackermann's function. In way, obtain same runtime as edge removal version problem, filling previously existing gap. Our algorithm finds application maintaining wireless networks undergoing transient station failures.