Paper Info
Title
On the approximability of some degree-constrained subgraph problems
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 Maximumd-degree-bounded Connected Subgraph (MDBCS"d) problem takes as additional input a weight function @w:E-R^+, and asks for a subset E^'@?E such that the subgraph induced by E^' is connected, has maximum degree at most d, and @?"e"@?"E"^"'@w(e) is maximized. The Minimum Subgraph of Minimum Degree=d (MSMD"d) problem involves finding a smallest subgraph of G with minimum degree at least d. Finally, the Dual Degree-densek-Subgraph (DDDkS) problem consists in finding a subgraph H of G such that |V(H)|@?k and the minimum degree in H is maximized.
Year
DOI
Venue
2012
10.1016/j.dam.2012.03.025
Discrete Applied Mathematics
Keywords
Field
DocType
maximum degree,smallest subgraph,additional input,subset e,minimum subgraph,subgraph h,natural degree-constrained subgraph problem,maximumd-degree-bounded connected subgraph,dual degree-densek-subgraph,minimum degree,hardness of approximation,approximation algorithms
Integer,Approximation algorithm,Graph,Discrete mathematics,Combinatorics,Weight function,Hardness of approximation,Induced subgraph isomorphism problem,Degree (graph theory),Mathematics,Subgraph isomorphism problem
Journal
Volume
Issue
ISSN
160
12
0166-218X
Citations 
PageRank 
References 
8
0.48
29
Authors
5
Name
Order
Citations
PageRank
Omid Amini112511.39
David Peleg26662824.19
Stéphane Pérennes322323.08
Ignasi Sau424337.18
Saket Saurabh52023179.50