New techniques for approximating optimal substructure problems in power-law graphs

DOI10.1016/J.TCS.2011.10.023MaRDI QIDQ443723zbMATH OpenOpenAlexFDO

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

Publication date 13 August 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.10.023

zbMATH Keywords

inapproximabilitypower-law graphscomplexity hardnessembedding techniquesinapproximability optimal substructure frameworkoptimal substructure problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• 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
• On the hardness of optimization in power-law graphs
• Approximation algorithms for optimization problems in random power-law graphs

Cites work

• scientific article; zbMATH DE number 3169205 (Why is no real title available?)
• scientific article; zbMATH DE number 2050468 (Why is no real title available?)
• scientific article; zbMATH DE number 6469213 (Why is no real title available?)
• A Random Graph Model for Power Law Graphs
• A random graph model for massive graphs
• Approximation hardness of dominating set problems in bounded degree graphs
• Automata, Languages and Programming
• Emergence of Scaling in Random Networks
• Graph theory with applications
• Inapproximability of vertex cover and independent set in bounded degree graphs
• Large cliques in a power-law random graph
• On a conditionally Poissonian graph process
• On the hardness of approximating minimum vertex cover
• On the hardness of optimization in power-law graphs
• Some APX-completeness results for cubic graphs

Cited in

(9)

• Minimum vertex cover in generalized random graphs with power law degree distribution
• Inapproximability of dominating set on power law graphs
• On the hardness of optimization 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
• Greed is good for deterministic scale-free networks
• Approximation algorithms for optimization problems in random power-law graphs
• Greed is good for deterministic scale-free networks
• Hardness complexity of optimal substructure problems on power-law graphs

This page was built for publication: New techniques for approximating optimal substructure problems in power-law graphs

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