View source for 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 | 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 ==

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