کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419411 | 683803 | 2012 | 19 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On the approximability of some degree-constrained subgraph problems On the approximability of some degree-constrained subgraph problems](/preview/png/419411.png)
In this article we provide hardness results and approximation algorithms for the following three natural degree-constrained subgraph problems, which take as input an undirected graph G=(V,E)G=(V,E). Let d≥2d≥2 be a fixed integer. The Maximumd−degree-bounded Connected Subgraph (MDBCSdMDBCSd) problem takes as additional input a weight function ω:E→R+ω:E→R+, and asks for a subset E′⊆EE′⊆E such that the subgraph induced by E′E′ is connected, has maximum degree at most dd, and ∑e∈E′ω(e)∑e∈E′ω(e) is maximized. The Minimum Subgraph of Minimum Degree≥d≥d (MSMDdMSMDd) problem involves finding a smallest subgraph of GG with minimum degree at least dd. Finally, the Dual Degree-densekk-Subgraph (DDDkSDDDkS) problem consists in finding a subgraph HH of GG such that |V(H)|≤k|V(H)|≤k and the minimum degree in HH is maximized.
Journal: Discrete Applied Mathematics - Volume 160, Issue 12, August 2012, Pages 1661–1679