An Average Case NP-complete Graph Colouring Problem.
Leonid A. LevinRamarathnam VenkatesanPublished in: Comb. Probab. Comput. (2018)
Keyphrases
- average case
- np complete
- graph colouring
- bin packing
- combinatorial problems
- round robin
- constraint satisfaction problems
- worst case
- tabu search
- np hard
- phase transition
- uniform distribution
- timetabling problem
- worst case analysis
- computational complexity
- learning curves
- constraint satisfaction
- average case complexity
- constraint programming
- load balancing
- global constraints
- neural network
- combinatorial optimization
- metaheuristic
- memetic algorithm
- sample complexity
- integer programming
- simulated annealing
- upper bound
- lower bound
- search algorithm