 | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (November 2024) (Learn how and when to remove this message) |
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
 | This graph theory-related article is a stub. You can help Misplaced Pages by expanding it. |