On the approximability of some degree-constrained subgraph problems

DOI10.1016/j.dam.2012.03.025zbMath1246.05040MaRDI QIDQ444431

Stéphane Pérennes, David Peleg, Saket Saurabh, Ignasi Sau, Omid Amini

Publication date: 14 August 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.03.025

zbMATH Keywords

approximation algorithms; hardness of approximation; degree-constrained subgraph

Mathematics Subject Classification ID

68W25: Approximation algorithms

05C07: Vertex degrees

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)