Title: Minimum Average Delay of Routing Trees
Authors: Saber Mirzaei
Date: January 11, 2016
Abstract:
The general communication tree embedding problem is the problem of
mapping a set of communicating terminals, represented by a graph G,
into the set of vertices of some physical network represented by a
tree T. In the case where the vertices of G are mapped into the
leaves of the host tree T the underlying tree is called a routing tree
and if the internal vertices of T are forced to have degree 3, the
host tree is known as layout tree. Different optimization problems
have been studied in the class of communication tree problems such as
well-known minimum edge dilation and minimum edge congestion
problems. In this report we study the less investigate measure
i.e. tree length, which is a representative for average edge dilation
(communication delay) measure and also for average edge congestion
measure. We show that finding a routing tree T for an arbitrary graph
G with minimum tree length is an NP-Hard problem.