On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs

DOI10.1007/978-3-642-17458-2_17zbMath1310.68096OpenAlexW1511446519MaRDI QIDQ3066157

My T. Thai, Yilin Shen, Dung Tien Nguyen

Publication date: 8 January 2011

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-17458-2_17

zbMATH Keywords

complexityinapproximabilitypower law graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (1)

Approximability of the vertex cover problem in power-law graphs

This page was built for publication: On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs