Hierarchical ring network design
type: Item
instance of: scholarly article
title: Hierarchical ring network design
zbMATH Open document ID: 1101.68315
author: Jean-Claude Bermond
author: Sébastien Choplin
author: Stéphane Pérennes
published in: Theory of Computing Systems
publication date: 2005-02-11T00:00:00Z
review text: A hierarchical ring network is obtained from a ring network by appending at most one subsidiary ring to each node of the ring and, recursively, to each node of each subsidiary ring. The depth d is the number of levels of the recursive appending of subsidiary rings. There are different definitions according to which rings are appended to nodes created at the preceding level (called an HRN) or to any node (called here an HBN for Hierarchical Bubble Network). The case of an HRN was considered by Aiello et al. who give bounds (not tight) on the diameter of such an HRN as a function of the depth and the number of nodes. Here we determine the exact order of the diameter both for an HRN and an HBN. In fact we consider the optimization problem of maximizing the number of nodes of an HBN (or an HRN) of given depth \(d\) and diameter D. We reduce the problem to a system of equations with a complex objective function. Solving this system enables us to determine precisely the structure of an optimal HBN and to show that the maximum number of nodes is of order \(D^ d /d!\).
Mathematics Subject Classification ID: 68M10
zbMATH DE Number: 2133729
MaRDI profile type: Publication
full work available at URL: s00224-003-1127-1
OpenAlex ID: W1988644897
DOI: 10.1007/S00224-003-1127-1
description: scientific article; zbMATH DE number 2133729