Show simple item record

dc.contributor.authorMirzaei, Saberen_US
dc.date.accessioned2017-04-26T18:43:39Z
dc.date.available2017-04-26T18:43:39Z
dc.date.issued2016-01-11
dc.identifier.citationMirzaei, Saber. Minimum Average Delay of Routing Trees. Technical Report BU-CS-TR 2016-001, Computer Science Department, Boston University, January 11, 2016.
dc.identifier.urihttps://hdl.handle.net/2144/21779
dc.description.abstractThe 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.en_US
dc.language.isoen_US
dc.publisherComputer Science Department, Boston Universityen_US
dc.relation.ispartofseriesBUCS Technical Reports;BUCS-TR-2016-001
dc.subjectCommunication treeen_US
dc.subjectMulti-graphsen_US
dc.titleMinimum average delay of routing treesen_US
dc.typeTechnical Reporten_US


This item appears in the following Collection(s)

Show simple item record