File(s) under permanent embargo
The maximum degree & diameter-bounded subgraph and its applications
journal contribution
posted on 2012-09-01, 00:00 authored by A Dekker, H Pérez-Rosés, Guillermo Pineda VillavicencioGuillermo Pineda Villavicencio, P WattersWe 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.
History
Journal
Journal of mathematical modelling and algorithmsVolume
11Issue
3Pagination
249 - 268Publisher
SpringerLocation
Cham, SwitzerlandPublisher DOI
ISSN
1570-1166eISSN
1572-9214Language
engPublication classification
C1.1 Refereed article in a scholarly journalUsage metrics
Categories
No categories selectedLicence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC