Tractability frontiers of the partner units configuration problem

作者：

Highlights：

• We prove that the Partner Units Problem (PUP) is NP-complete for various important subclasses.

• We present a poly-time algorithm for a PUP subclass which lies in P.

• We give in-depth worst-case complexity results for the presented algorithm.

摘要

•We prove that the Partner Units Problem (PUP) is NP-complete for various important subclasses.•We present a poly-time algorithm for a PUP subclass which lies in P.•We give in-depth worst-case complexity results for the presented algorithm.

论文关键词：Partner units problem,Computational complexity,NP-completeness

论文评审过程：Received 20 January 2015, Revised 6 November 2015, Accepted 7 December 2015, Available online 21 March 2016, Version of Record 1 April 2016.

论文官网地址：https://doi.org/10.1016/j.jcss.2015.12.004