The maximum degree & diameter-bounded subgraph and its applications

Title: The maximum degree & diameter-bounded subgraph and its applications
Creator: Dekker, Anthony; Pérez-Rosés, Hebert; Pineda-Villavicencio, Guillermo; Watters, Paul
Date: 2012
Type: Text; Journal article
Identifier: http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/73285
Identifier: vital:7040
Identifier: https://doi.org/10.1007/s10852-012-9182-8
Identifier: ISSN:1570-1166
Abstract: We introduce the problem of finding the largest subgraph of a given weighted undirected graph (host graph), subject to constraints on the maximum degree and the diameter. We discuss some applications in security, network design and parallel processing, and in connection with the latter we derive some bounds for the order of the largest subgraph in host graphs of practical interest: the mesh and the hypercube. We also present a heuristic strategy to solve the problem, and we prove an approximation ratio for the algorithm. Finally, we provide some experimental results with a variety of host networks, which show that the algorithm performs better in practice than the prediction provided by our theoretical approximation ratio.
Relation: Journal of Mathematical Modelling and Algorithms Vol. 11, no. 3 (2012), p. 249-268
Rights: Copyright Springer
Rights: This metadata is freely available under a CCO license
Subject: Network design; Degree/diameter problem; Botnets; Mesh
Reviewed