An optimal online strategy to increment connection trees

Constructing a tree spanning a given subset of vertices of a graph is a generic problem that has been extensively studied (for example the classical Steiner tree is one of them). In this paper, we propose to take into account a problem that has not been often studied: the dynamic part, in which new vertices must be inserted in a given tree. We propose to do these insertions with respect of structural constraints that we describe and to capture the efficiency of algorithms by a particular type of competitive ratios. The parameter to optimize in our study is related to distances between the connected vertices. Our main results are the following. We propose a method, called median-addition. We prove that its competitive ratio is non constant but optimal. This result is proved under the hypothesis that the algorithm does not know the sequence of added vertices (called unknown-future or online model). This method can be used to design communication structures for applications like video-conference in networks for example. In another part of the paper, we prove the surprising following result: even if the algorithm knows the sequence of additions of new vertices (hence everything is known in advance), no algorithm can have a constant competitive ratio.