The Maximum Degree-and-Diameter-Bounded Subgraph Problem

Introduction

Given a connected host graph G, an upper bound for the degree d, and an upper bound for the diameter k, we look for the largest subgraph S of G with maximum degree at most d and diameter at most k. This problem contains the Degree-Diameter Problem as a special case (namely, by taking a sufficiently large complete graph as a host graph). The problem was defined in (Dekker et al, 2011), where some applications were discussed, and a polynomial-time approximation algorithm was proposed. Regarding its computational complexity, the problem is NP-hard, and not in APX (i.e. it cannot be approximated to within a constant factor in polynomial time).

MaxDDBS in special classes of host networks

MaxDDBS in the mesh

MaxDDBS in the honeycomb

MaxDDBS in the hypercube

References

1. Dekker, Anthony; Perez-Roses, Hebert; Pineda-Villavicencio, Guillermo; Watters, Paul (2011), "The Maximum Degree&Diameter-Bounded Subgraph and its Applications". Journal of Mathematical Modelling and Algorithms. DOI 10.1007/s10852-012-9182-8.
2. Miller, Mirka; Perez-Roses, Hebert; Ryan, Joe (2011), "The Maximum Degree&Diameter-Bounded Subgraph in the Mesh", to appear in Discrete Applied Mathematics.