Approximation algorithms for optimization problems in random power-law graphs

DOI10.1007/978-3-319-12691-3_26MaRDI QIDQ2942410zbMATH OpenOpenAlexFDO

Authors Yilin Shen, Xiang Li, My T. Thai

Publication date 11 September 2015

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

Full work available at URL https://doi.org/10.1007/978-3-319-12691-3_26

zbMATH Keywords

approximation algorithmspower-law graphsprobabilistic analysisrandom graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs
• New techniques for approximating optimal substructure problems in power-law graphs
• Hardness complexity of optimal substructure problems on power-law graphs
• On the Hardness of Optimization in Power Law Graphs
• On the hardness of optimization in power-law graphs

Cited in

(7)

• Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
• On the hardness of optimization in power-law graphs
• Hardness complexity of optimal substructure problems on power-law graphs
• On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs
• On the Hardness of Optimization in Power Law Graphs
• New techniques for approximating optimal substructure problems in power-law graphs
• scientific article; zbMATH DE number 1857640 (Why is no real title available?)

This page was built for publication: Approximation algorithms for optimization problems in random power-law graphs

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