On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs.
Yilin ShenDung T. NguyenMy T. ThaiPublished in: COCOA (1) (2010)
Keyphrases
- power law
- optimization problems
- small world
- real world graphs
- evolutionary algorithm
- degree distribution
- scale free
- power laws
- random graphs
- metaheuristic
- cost function
- np hard
- approximation algorithms
- learning curves
- objective function
- preferential attachment
- power law distribution
- long range correlations
- clustering coefficient
- traveling salesman problem
- phase transition
- combinatorial optimization
- directed graph
- np complete
- special case
- genetic algorithm