Skip to main navigation Skip to search Skip to main content

On the approximability of some degree-constrained subgraph problems

  • Omid Amini
  • , David Peleg
  • , Stéphane Pérennes
  • , Ignasi Sau
  • , Saket Saurabh
  • Weizmann Institute of Science Israel
  • Centre national de la recherche scientifique
  • DALI/LIRMM
  • Institute of Mathematical Sciences India

Research output: Contribution to journal › Article › peer-review

19 Citations (Scopus)

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 (MDBCSd) problem takes as additional input a weight function ω: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′ω(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-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.

Original languageEnglish
Pages (from-to)1661-1679
Number of pages19
JournalDiscrete Applied Mathematics
Volume160
Issue number12
DOIs
Publication statusPublished - 1 Aug 2012

Keywords

  • Approximation algorithms
  • Degree-constrained subgraph
  • Hardness of approximation

Fingerprint

Dive into the research topics of 'On the approximability of some degree-constrained subgraph problems'. Together they form a unique fingerprint.

Cite this