Approximation Complexity of Max-Cut on Power Law Graphs.
Mikael GastMathias HauptmannMarek KarpinskiPublished in: CoRR (2016)
Keyphrases
- multiscale
- max cut
- power law
- spectral graph
- graph model
- small world
- planar graphs
- np complete problems
- scale free
- graph partitioning
- np hard
- real world graphs
- np complete
- degree distribution
- min max
- random graphs
- approximation algorithms
- power law distribution
- worst case
- computational complexity
- clustering coefficient
- hard problems
- decision problems