On the complexity of partitioning graphs into connected subgraphs |
| |
| Authors: | M.E. Dyer A.M. Frieze |
| |
| Affiliation: | Dept. of Mathematics and Statistics, Teesside Polytechnic, Middlesborough, Cleveland TS1 3BA, United Kingdom;Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA 15213, USA |
| |
| Abstract: | This paper is mainly concerned with the computational complexity of determining whether or not the vertices of a graph can be partitioned into equal sized subsets so that each subset induces a particular type of graph. Many of the NP-completeness results are for planar graphs. These are proved using a planar version of 3-dimensional matching. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
