scientific article; zbMATH DE number 4012499

From MaRDI portal
Publication:3762227





[For the entire collection see Zbl 0619.00006.] The design problem in communication networks is placed in a combinatorial setting by modelling a network as a graph where vertices represent processor sites and edges represent links. Given this model and some constraints, we seek the best network with respect to some measure of reliability. One widely-known measure is the probability that a network remains connected in an environment of fault-free processors and (statistically independent) link failures. When all edges fail with uniform probability p, reliability is directly related to connected spanning subgraph counts for \(p=\). Since networks are subject to change, we address the network expansion problem: how do we optimally add a new link to an existing network? The design problem becomes: how do we design reliable networks with future expansion in mind? The latter problem is {\#}P-Complete in general; therefore we consider series-parallel graphs and a related class of graphs, a generalization of wheels. In particular, we show the best generalized wheel has maximum diameter.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3762227)