MaxDDBS Problem on Beneš Network
Novi H. Bong, JOE RYAN, Kiki Ariyanti Sugeng · Journal of Interconnection Networks · 2017
Maximum degree-diameter bounded subgraph problem is a problem of constructing the largest possible subgraph of given degree and diameter in a graph. This problem can be considered as a degree-diameter problem restricted to certain host graphs. The MaxDDBS problem with Beneš network as the host graph is discussed in this paper. Beneš network contains a back-to-back buttery network. Even though both networks have maximum degree 4, the structure of their maximum subgraphs are different. We give the constructive lower bound of the largest subgraph of Beneš network of various maximum degrees.