Routing Tree Problems on Random Graphs.
Carme Àlvarez, R. Ferrer Cases, Josep Dı́az, Jordi Petit, Marı́a Serna · 2000
this paper we are interested in the complexity of finding routing trees minimizing some measures. We consider an unweighted complete graph as the communication net. We require that the routing tree has internal nodes of degree 3, and all the terminals must be the leaves of the routing tree. Furthermore, the communication requirements between terminals is 0 or 1. The particular measures that we will minimize are congestion, dilation and total communication cost (see definitions below). We will refer to these problems as the routing tree