On the Hardness of Optimization in Power Law Graphs
DOI10.1007/978-3-540-73545-8_41zbMATH Open1206.05096OpenAlexW1710013235MaRDI QIDQ3608866FDOQ3608866
Kihong Park, Alessandro Ferrante, Gopal Pandurangan
Publication date: 6 March 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-73545-8_41
Recommendations
- On the hardness of optimization in power-law graphs
- Hardness complexity of optimal substructure problems on power-law graphs
- On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs
- New techniques for approximating optimal substructure problems in power-law graphs
- Approximation algorithms for optimization problems in random power-law graphs
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) Abstract computational complexity for mathematical programming problems (90C60) Vertex degrees (05C07)
Cited In (9)
- Finding Cliques in Social Networks: A New Distribution-Free Model
- Connections in Networks: Hardness of Feasibility Versus Optimality
- Decompositions of triangle-dense graphs
- Title not available (Why is that?)
- On the hardness of optimization in power-law graphs
- Hardness Results and Efficient Algorithms for Graph Powers
- On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs
- Title not available (Why is that?)
- On positive-influence target-domination
This page was built for publication: On the Hardness of Optimization in Power Law Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3608866)
