Hardness complexity of optimal substructure problems on power-law graphs

DOI10.1007/978-1-4614-0754-6_10MaRDI QIDQ2913785zbMATH OpenOpenAlexFDO

Authors Yilin Shen, My T. Thai, Dung T. Nguyen

Publication date 27 September 2012

Published in Handbook of Optimization in Complex Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-1-4614-0754-6_10

zbMATH Keywords

maximum cliquemaximum independent setminimum coloringminimum vertex coverminimum dominating set\(\rho \)-minimum dominating set

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• New techniques for approximating optimal substructure problems in power-law graphs
• On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs
• 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

Cited in

(8)

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

This page was built for publication: Hardness complexity of optimal substructure problems on power-law graphs

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