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

DOI10.1016/j.tcs.2011.10.023zbMath1243.68188OpenAlexW2008945309MaRDI QIDQ443723

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

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

Related Items (3)

Minimum vertex cover in generalized random graphs with power law degree distribution ⋮ Greed is good for deterministic scale-free networks ⋮ Inapproximability of dominating set on power law graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the hardness of approximating minimum vertex cover
• Approximation hardness of dominating set problems in bounded degree graphs
• Some APX-completeness results for cubic graphs
• On the hardness of optimization in power-law graphs
• A Random Graph Model for Power Law Graphs
• Large Cliques in a Power-Law Random Graph
• Emergence of Scaling in Random Networks
• A random graph model for massive graphs
• On a conditionally Poissonian graph process
• Automata, Languages and Programming

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