Optimum Network Partitioning

The problem of finding the optimum partition of a set of objects into disjoint collectively exhaustive subsets has been treated by several authors as a special set-covering problem. This paper considers this problem when the objects can be represented as nodes in a directed acyclical network and the subsets of the partition define subnetworks of the original network. A dynamic-programming algorithm is presented that solves the latter problem. This algorithm is, in some important cases, more efficient than the implicit-enumeration schemes that have been previously proposed for the more general set-partitioning problem.