|
The Maximum Degree-and-Diameter-Bounded Subgraph problem (MaxDDBS) is a problem in graph theory. 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 is also referred to as the Degree-Diameter Subgraph Problem, as it contains the degree diameter problem as a special case (namely, by taking a sufficiently large complete graph as a host graph). Despite being a natural generalization of the Degree-Diameter Problem, MaxDDBS only began to be investigated in 2011, while research in the Degree-Diameter Problem has been active since the 1960s. 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). == References == # ( The MaxDDBS page in Combinatorics Wiki ) # A.Dekker, H.Perez-Roses, G.Pineda-Villavicencio, and P.Watters. The Maximum Degree & Diameter-Bounded Subgraph and its Applications. Journal of Mathematical Modelling and Algorithms, 2012. DOI: 10.1007/s10852-012-9182-8 # M.Miller, H.Perez-Roses, and J.Ryan. The Maximum Degree and Diameter Bounded Subgraph in the Mesh. Discrete Applied Mathematics, 2012. DOI: 10.1016/j.dam.2012.03.035 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「MaxDDBS」の詳細全文を読む スポンサード リンク
|