Hardness complexity of optimal substructure problems on power-law graphs
DOI10.1007/978-1-4614-0754-6_10zbMATH Open1250.05102OpenAlexW48444036MaRDI QIDQ2913785FDOQ2913785
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
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
maximum cliquemaximum independent setminimum coloringminimum vertex coverminimum dominating set\(\rho \)-minimum dominating set
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)
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)
