One way to factorize an integer is via the recursive process of identifying a factor at a time. A polynomial, or more generally, an element in a unique factorization domain can also be factorized into primes, which cannot be further factorized. Bearing the same spirit, many other types of mathematical objects can also be recursively factorized in similar fashions. Examples include Abelian groups, stationary Markov chains and invariant measures. The characteristic of the prime factorization for each type of objects depends on their algebraic structure. For instance, it yields the product of prime factors as well as a unit factor in the case of a unique factorization domain.
A “network” means a set of nodes interconnected by links. An exemplifying network consists of service centers interconnected by channels for the interflow traffic of service requests. In the abstract form, a network is called a graph and the links interconnecting the nodes are called edges.
A network partition is to classify the vertices into classes according to a given template, an algorithmic approach to find a maximum network partition naturally leads to a network factorization, where a graph is decomposed into prime pieces through removing a factorizer. Since a graph by itself lacks the necessary algebraic structure to create such a sense of prime factorization, the notion of a “template” is coined so that network factorization is always with respect to a predetermined template. Different templates can lead to drastically different ways of factorization.
The classical matching is a special case of network partition and network factorization, although there is a fundamental difference between the viewpoints. A graph that does not possess a perfect matching is regarded as being “deficient” in the matching theory. Network partition and network factorization theory, on the other hand, treats such deficiency as “complexity.” The more deficient a graph is, the higher the complexity. Thus network factorization decomposes a graph into subgraphs of minimal complexities. To motivate this new concept, Chapter 1 reviews the basic matching theory in the language of a special form of network factorization.
Then Chapter 2 sets up the notion of a template and the general concept of network factorization with respect to a template. At the same time, the variety of templates of interest is reduced through equivalence to just those templates Xn and Dn, where n ³ 2. Matching coincides with network factorization with respect to X2. The remaining chapters then deal with network factorization with respect to D2, Xn and Dn, where n ³
The prime factorization theory of networks traces back to an unpublished manuscript [37] of S.-Y. R. Li in 1978, which was intended for a paper. The theory grew in length over time, and a summary [38] was tentatively published in a conference in 1993. Y. X. Yang joined the effort in scrutinizing the technical detail during the early 1990’s. The writing and publishing process however still lagged behind. A recent collaborative work with G. Han at the Institute of Network Coding of The Chinese University of Hong Kong finally brought the lengthy process to a closure.