Partitioning an Assembly into Connected Parts is NP-hard

L. E. Kavraki and M. N. Kolountzakis, “Partitioning an Assembly into Connected Parts is NP-hard,” Information Processing Letters, vol. 55, pp. 159–165, 1995.

Publisher: http://dx.doi.org/10.1016/0020-0190(95)00083-O

PDF preprint: http://kavrakilab.org/publications/kavraki-kolountzakis1995partitioning-assembly-into.pdf