View source for MaxDDBS in the mesh

== The mesh as host graph ==

An important special case is when the host graph ''G'' is a common parallel architecture, such as the mesh, the hypercube, the butterfly, etc. The paper by Miller, Perez-Roses, and Ryan (2011) computes upper and lower bounds for the largest subgraph of the mesh in arbitrary dimension. Moreover, it discusses the cases of degree 4 in dimension 3, and degree 3 in dimension 2, where some general constructions are given, that are asymptotically optimal. 

[[The Maximum Degree-and-Diameter-Bounded Subgraph Problem | Back to MaxDDBS]]


=== Subgraphs of degree 3 in the 2-dimensional mesh ===

If we take an infinite 2-dimensional mesh as a host graph, then the only case that makes sense is ''d''=3. In this case, the upper bound for the order of the largest subgraph is: 

* <math> 2p^2 + 2p +1 </math>, if ''k'' is even, and 
* <math> 2p^2 + 4p +2 </math>, if ''k'' is odd, 

where <math> p = \lfloor k/2 \rfloor </math>. 

The paper by Miller, Perez-Roses and Ryan (2011) gives general constructions for this case, that come asymptotically close to the upper bounds. However, for particular values of the diameter, the constructions do not provide the largest known subgraphs. Here we maintain a list of the largest known subgraphs of degree 3 for some small values of the diameter ''k''.

The following table gives the order of the largest known subgraphs. If you can beat any of these constructions, please get in contact with the  [mailto:hebert.perez@gmail.com moderator] in order to include your graph:  


<center> 
{| border="1" cellspacing="2" cellpadding="2" style="text-align: center;"
| diameter '''<math>k</math>'''||  '''2'''||  '''3'''||  '''4''' ||  '''5''' ||  '''6''' ||  '''7''' ||  '''8'''|| '''9''' ||  '''10''' || '''11''' ||  '''12'''  ||  '''13'''  ||  '''14'''  ||  '''15'''  ||  '''16''' 
|-
| best upper bound || style="background-color: white; text-align: center;" | 4 || style="background-color: white; text-align: center;" | 6 || style="background-color: white; text-align: center;" | 10 || style="background-color: white; text-align: center;" | 14 || style="background-color: white; text-align: center;" | 22 || style="background-color: white; text-align: center;" | 32 ||style="background-color: white; text-align: center;" | 41 || style="background-color: white; text-align: center;" | 50 || style="background-color: white; text-align: center;" | 61 ||style="background-color: white; text-align: center;" | 72 ||style="background-color: white; text-align: center;" | 85 ||style="background-color: white; text-align: center;" | 98 ||style="background-color: white; text-align: center;" | 113 ||style="background-color: white; text-align: center;" | 128 ||style="background-color: white; text-align: center;" | 145 
|-
| order of largest graph  || style="background-color: #FF9900; text-align: center;" | 4 || style="background-color: #FF9900; text-align: center;" | 6 || style="background-color: #FF9900; text-align: center;" | 10 || style="background-color: #FF9900; text-align: center;" | 14 || style="background-color: #FF9900; text-align: center;" | 22 || style="background-color: #cccccc; text-align: center;" | 28 || style="background-color: #cccccc; text-align: center;" | 37 || style="background-color: #cccccc; text-align: center;" | 44 ||style="background-color: #cccccc; text-align: center;" | 52 || style="background-color: #cccccc; text-align: center;" | 68 || style="background-color: #cccccc; text-align: center;" | 77 || style="background-color: #cccccc; text-align: center;" | 90 || style="background-color: #cccccc; text-align: center;" | 104 || style="background-color: #cccccc; text-align: center;" | 124 || style="background-color: #cccccc; text-align: center;" | 135 
|-
| percent of upper bound || style="background-color: white; text-align: center;" | 100 || style="background-color: white; text-align: center;" | 100 || style="background-color: white; text-align: center;" | 100 || style="background-color: white; text-align: center;" | 100 || style="background-color: white; text-align: center;" | 100 || style="background-color: white; text-align: center;" | 87.5 ||style="background-color: white; text-align: center;" | 90.2 || style="background-color: white; text-align: center;" | 88 || style="background-color: white; text-align: center;" | 85.2 ||style="background-color: white; text-align: center;" | 94.4 ||style="background-color: white; text-align: center;" | 90.5 ||style="background-color: white; text-align: center;" | 91.8 ||style="background-color: white; text-align: center;" | 92 ||style="background-color: white; text-align: center;" | 96.8 ||style="background-color: white; text-align: center;" | 93 
|}
</center>


Next is the table with the color codes: 


<center>
{| border="1" cellspacing="1" cellpadding="1" style="text-align: left;"
|'''Color''' || style="text-align: center;" |'''Details'''
|-
|style="background-color: #cccccc; text-align: center;" | * || Graphs found by Hebert Perez-Roses, Mirka Miller, and Joe Ryan 
|-
|style="background-color: #FF9900; text-align: center;" | * || Optimal graphs found by Anthony Dekker by exhaustive search 
|}
</center>


And the actual graphs are shown here: 

                        Diameters 2, 3, 4: 

[[Image:Delta3-Diam234.jpg|center|300px|Diameters 2, 3, 4]] 

                        Diameter 5: 

[[Image:Delta3-Diam5.jpg|center|130px|Diameter 5, order 14]] 

                        Diameter 6: 

[[Image:Delta3-Diam6.jpg|center|150px|Diameter 6, order 22]] 

                        Diameter 7: 

[[Image:Delta3-Diam7.jpg|center|170px|Diameter 7, order 28]] 

                        Diameter 8: 

[[Image:Delta3-Diam8.jpg|center|180px|Diameter 8, order 37]]

                        Diameter 9: 

[[Image:Delta3-Diam9.jpg|center|190px|Diameter 9, order 44]]

                        Diameter 10: 

[[Image:Delta3-Diam10.jpg|center|200px|Diameter 10, order 52]]

                        Diameter 11: 

[[Image:Delta3-Diam11.jpg|center|220px|Diameter 11, order 68]] 

                        Diameter 12: 

[[Image:Delta3-Diam12.jpg|center|235px|Diameter 12, order 77]]

                        Diameter 13: 

[[Image:Delta3-Diam13.jpg|center|250px|Diameter 13, order 90]]

                        Diameter 14: 

[[Image:Delta3-Diam14.jpg|center|265px|Diameter 14, order 104]]

                        Diameter 15: 

[[Image:Delta3-Diam15B.jpg|center|280px|Diameter 15, order 124]]

                        Diameter 16: 

[[Image:Delta3-Diam16.jpg|center|295px|Diameter 16, order 135]]

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