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

DOI10.1007/978-3-642-17458-2_17MaRDI QIDQ3066157zbMATH OpenOpenAlexFDO

Authors Yilin Shen, My T. Thai, Dung T. 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

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) 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) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Recommendations

• On the hardness of optimization in power-law graphs
• On the Hardness of Optimization in Power Law Graphs
• Approximation algorithms for optimization problems in random power-law graphs
• Hardness complexity of optimal substructure problems on power-law graphs
• Inapproximability of dominating set on power law graphs
• Approximability of the vertex cover problem in power-law graphs
• Hardness Results and Efficient Algorithms for Graph Powers
• New techniques for approximating optimal substructure problems in power-law graphs
• Complexity and inapproximability results for the power edge set problem
• Algorithms and complexity of power domination in graphs

Cited in

(11)

• Complexity and inapproximability results for the power edge set problem
• Greed is good for deterministic scale-free networks
• On the hardness of optimization in power-law graphs
• Hardness complexity of optimal substructure problems on power-law graphs
• Approximation algorithms for optimization problems in random power-law graphs
• On the Hardness of Optimization in Power Law Graphs
• Approximability of the vertex cover problem in power-law graphs
• New techniques for approximating optimal substructure problems in power-law graphs
• Greed is good for deterministic scale-free networks
• Inapproximability of dominating set on power law graphs
• Hardness Results and Efficient Algorithms for Graph Powers

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3066157)