The maximum degree & diameter-bounded subgraph and its applications

Anthony Dekker, Hebert Pérez-Rosés*, Guillermo Pineda-Villavicencio, Paul Watters

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)249-268
Number of pages20
JournalJournal of Mathematical Modelling and Algorithms
Volume11
Issue number3
DOIs
Publication statusPublished - Sept 2012
Externally publishedYes

Keywords

  • Botnets
  • Degree/diameter problem
  • Mesh
  • Network design

Fingerprint

Dive into the research topics of 'The maximum degree & diameter-bounded subgraph and its applications'. Together they form a unique fingerprint.

Cite this