http://combinatoricswiki.org/index.php?action=history&feed=atom&title=The_Maximum_Degree-and-Diameter-Bounded_Subgraph_ProblemThe Maximum Degree-and-Diameter-Bounded Subgraph Problem - Revision history2026-05-21T22:37:26ZRevision history for this page on the wikiMediaWiki 1.31.1http://combinatoricswiki.org/index.php?title=The_Maximum_Degree-and-Diameter-Bounded_Subgraph_Problem&diff=317&oldid=prevGrahame: 1 revision imported2019-01-03T14:39:33Z<p>1 revision imported</p>
<table class="diff diff-contentalign-left" data-mw="interface">
<tr class="diff-title" lang="en-GB">
<td colspan="1" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="1" style="background-color: #fff; color: #222; text-align: center;">Revision as of 14:39, 3 January 2019</td>
</tr><tr><td colspan="2" class="diff-notice" lang="en-GB"><div class="mw-diff-empty">(No difference)</div>
</td></tr></table>Grahamehttp://combinatoricswiki.org/index.php?title=The_Maximum_Degree-and-Diameter-Bounded_Subgraph_Problem&diff=316&oldid=prevCW>Hebert: /* References */2012-03-19T20:03:28Z<p><span dir="auto"><span class="autocomment">References</span></span></p>
<p><b>New page</b></p><div>== Introduction ==<br />
<br />
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).<br />
<br />
== MaxDDBS in special classes of host networks ==<br />
<br />
[[MaxDDBS in the mesh]]<br />
<br />
[[MaxDDBS in the honeycomb]]<br />
<br />
[[MaxDDBS in the hypercube]]<br />
<br />
== References ==<br />
<br />
# 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.<br />
# Miller, Mirka; Perez-Roses, Hebert; Ryan, Joe (2011), "The Maximum Degree&Diameter-Bounded Subgraph in the Mesh", to appear in ''Discrete Applied Mathematics''.</div>CW>Hebert