k-L(2, 1)-labelling for planar graphs is NP-complete for k>=4.

Nicole Eggemann Frédéric Havet Steven D. Noble

Published in: Discret. Appl. Math. (2010)

Keyphrases

np complete
planar graphs
computational complexity
np hard
minimum weight
phase transition
approximate inference
bayesian networks
belief propagation
np complete problems
social networks
stereo matching
weighted graph