Degree-Constrained Subgraph Problems: Hardness and Approximation Results
From MaRDI portal
Publication:3602827
DOI10.1007/978-3-540-93980-1_3zbMath1209.68629MaRDI QIDQ3602827
Stéphane Pérennes, David Peleg, Saket Saurabh, Ignasi Sau, Omid Amini
Publication date: 12 February 2009
Published in: Approximation and Online Algorithms (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/inria-00331747/file/Amply_bis.pdf
approximation algorithms; hardness of approximation; PTAS; excluded minor; APX; degree-constrained subgraphs
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
