Optimal MST Maintenance for Transient Deletion of every Node in Planar Graphs

摘要

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