The antibandwidth problem is to label vertices of a n-vertex graph injectively by 1, 2, 3, ... n, such that the minimum difference of labels of adjacent vertices is maximised. The problem is motivated by obnoxious facility location problem, radiocolouring, work and game scheduling and is dual to the well known bandwidth problem. We prove exact results for the antibandwidth of complete k-ary trees, k even, and estimate the parameter for odd k up to the second order term. This extends previous results for complete binary trees. © 2006 Elsevier B.V. All rights reserved.
Antibandwidth of Complete k-Ary Trees / Calamoneri, Tiziana; Massini, Annalisa; L˘ubomir, Torok; I., Vrto. - ELETTRONICO. - 24:(2006), pp. 259-266. (Intervento presentato al convegno 5-th Cracow Conference on Graph Theory tenutosi a Ustron; Poland nel September 11-15, 2006) [10.1016/j.endm.2006.06.028].
Antibandwidth of Complete k-Ary Trees
CALAMONERI, Tiziana;MASSINI, Annalisa;
2006
Abstract
The antibandwidth problem is to label vertices of a n-vertex graph injectively by 1, 2, 3, ... n, such that the minimum difference of labels of adjacent vertices is maximised. The problem is motivated by obnoxious facility location problem, radiocolouring, work and game scheduling and is dual to the well known bandwidth problem. We prove exact results for the antibandwidth of complete k-ary trees, k even, and estimate the parameter for odd k up to the second order term. This extends previous results for complete binary trees. © 2006 Elsevier B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
