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

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