Difference between revisions of "The Maximum DegreeandDiameterBounded Subgraph Problem"
From Combinatorics Wiki
CW>Hebert (→References) 
m (1 revision imported) 
(No difference)

Latest revision as of 14:39, 3 January 2019
Introduction
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 contains the DegreeDiameter Problem as a special case (namely, by taking a sufficiently large complete graph as a host graph). The problem was defined in (Dekker et al, 2011), where some applications were discussed, and a polynomialtime approximation algorithm was proposed. Regarding its computational complexity, the problem is NPhard, and not in APX (i.e. it cannot be approximated to within a constant factor in polynomial time).
MaxDDBS in special classes of host networks
References
 Dekker, Anthony; PerezRoses, Hebert; PinedaVillavicencio, Guillermo; Watters, Paul (2011), "The Maximum Degree&DiameterBounded Subgraph and its Applications". Journal of Mathematical Modelling and Algorithms. DOI 10.1007/s1085201291828.
 Miller, Mirka; PerezRoses, Hebert; Ryan, Joe (2011), "The Maximum Degree&DiameterBounded Subgraph in the Mesh", to appear in Discrete Applied Mathematics.