# The Maximum Degree-and-Diameter-Bounded Subgraph Problem

From Combinatorics Wiki

Revision as of 20:03, 19 March 2012 by CW>Hebert (→References)

## 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

## References

- 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. - Miller, Mirka; Perez-Roses, Hebert; Ryan, Joe (2011), "The Maximum Degree&Diameter-Bounded Subgraph in the Mesh", to appear in
*Discrete Applied Mathematics*.