The polynomial dichotomy for three nonempty part sandwich problems

作者：Teixeira Rafael B^*; Dantas Simone; de Figueiredo Celina M H

来源：Discrete Applied Mathematics, 2010, 158(12): 1286-1304.

DOI：10.1016/j.dam.2009.12.002

• Graph partitions
• Sandwich problems
• Graph algorithms
• Computational complexity
• Structural characterization of graphs
• NP-complete

We classify into polynomial time or NP-complete all three nonempty part sandwich problems. This solves the polynomial dichotomy into polynomial time and NP-complete for this class of graph partition problems.

• 出版日期2010-6-28