On the hardness of optimization in power-law graphs

DOI10.1016/j.tcs.2007.12.007zbMath1135.68512MaRDI 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-hardness; power-law graphs; graph optimization problems; graph construction algorithms

Mathematics Subject Classification ID

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

Related Items

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