On the hardness of optimization in power-law graphs

DOI10.1016/j.tcs.2007.12.007zbMath1135.68512OpenAlexW2008138618MaRDI QIDQ2481967

Alessandro Ferrante, Kihong Park, Gopal Pandurangan

Publication date: 15 April 2008

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

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

zbMATH Keywords

NP-hardnesspower-law graphsgraph optimization problemsgraph construction algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (11)

Approximability of the vertex cover problem in power-law graphs ⋮ On positive influence dominating sets in social networks ⋮ Finding Cliques in Social Networks: A New Distribution-Free Model ⋮ Unnamed Item ⋮ Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket ⋮ Greed is good for deterministic scale-free networks ⋮ New techniques for approximating optimal substructure problems in power-law graphs ⋮ Inapproximability of dominating set on power law graphs ⋮ The Complexity and Approximability of Minimum Contamination Problems ⋮ On the approximability of positive influence dominating set in social networks ⋮ Modeling and Designing Real–World Networks

Cites Work

• Unnamed Item
• Unnamed Item
• The diameter of a scale-free random graph
• A Random Graph Model for Power Law Graphs
• A random graph model for massive graphs
• Node-and edge-deletion NP-complete problems
• Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications

This page was built for publication: On the hardness of optimization in power-law graphs