Sharper Lower Bounds in the Maximum Degree and Diameter Bounded Subgraph Problem in the Mesh

Sachi Hashimoto

The Maximum Degree and Diameter Bounded Subgraph Problem (MaxDDBS) asks: given a host graph G, a bound on maximum degree Δ, and a diameter D, what is the largest subgraph of the ho…