Article ID Journal Published Year Pages File Type
419537 Discrete Applied Mathematics 2010 19 Pages PDF
Abstract

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.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
The polynomial dichotomy for three nonempty part sandwich problems
Authors
, , ,