Publications

This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  2003, with author ALL, in the category IASI Research Reports (or show them all):


IASI Research Report n. 586  (Previous    Next)


Carlo Gaibisso, Guido Proietti, Tan R.

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

ABSTRACT
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 .........., 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 .............. 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.
back
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -