Amini, Omid ; Peleg, David ; Pérennes, Stéphane ; Sau, Ignasi ; Saurabh, Saket
(2012)
*On the approximability of some degree-constrained subgraph problems*
Discrete Applied Mathematics, 160
(12).
pp. 1661-1679.
ISSN 0166-218X

Full text not available from this repository.

Official URL: http://doi.org/10.1016/j.dam.2012.03.025

Related URL: http://dx.doi.org/10.1016/j.dam.2012.03.025

## Abstract

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). Let d ≥ 2 be a fixed integer. The Maximum d-degree-bounded Connected Subgraph (MDBCSd) problem takes as additional input a weight function ω : E → R + , and asks for a subset E 0 ⊆ E such that the subgraph induced by E 0 is connected, has maximum degree at most d, and P e∈E0 ω(e) is maximized. The Minimum Subgraph of Minimum Degree ≥ d (MSMDd) problem involves finding a smallest subgraph of G with minimum degree at least d. Finally, the Dual Degree-dense k-Subgraph (DDDkS) problem consists in finding a subgraph H of G such that |V(H)| ≤ k and the minimum degree in H is maximized.

Item Type: | Article |
---|---|

Source: | Copyright of this article belongs to Elsevier Science. |

ID Code: | 123457 |

Deposited On: | 20 Sep 2021 07:57 |

Last Modified: | 20 Sep 2021 07:57 |

Repository Staff Only: item control page