On the connectivity preserving minimum cut problem

作者：

Highlights：

• We study an important generalization of the minimum cut problem (CPMC).

• We proved several important hardness results for the CPMC problem.

• We proved that planar CPMEC is in P.

摘要

•We study an important generalization of the minimum cut problem (CPMC).•We proved several important hardness results for the CPMC problem.•We proved that planar CPMEC is in P.

论文关键词：Minimum cut,Inapproximability,Connectivity preserving

论文评审过程：Received 14 February 2012, Revised 26 November 2013, Accepted 8 January 2014, Available online 15 January 2014.

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