Inapproximability of dominating set on power law graphs.
Mikael GastMathias HauptmannMarek KarpinskiPublished in: Theor. Comput. Sci. (2015)
Keyphrases
- power law
- dominating set
- connected dominating set
- facility location problem
- approximation algorithms
- small world
- degree distribution
- real world graphs
- power laws
- scale free
- random graphs
- power law distribution
- preferential attachment
- special case
- clustering coefficient
- long range correlations
- graph theoretic
- graph mining
- network structure