Excessive factorizations of bipartite multigraphs |
| |
Authors: | David Cariolaro Romeo Rizzi |
| |
Institution: | a Department of Mathematical Sciences, Xi’an Jiaotong-Liverpool University, Suzhou, Jiangsu 215213, Chinab Dipartimento di Matematica ed Informatica, Università di Udine, Italy |
| |
Abstract: | An excessive factorization of a multigraph G is a set F={F1,F2,…,Fr} of 1-factors of G whose union is E(G) and, subject to this condition, r is minimum. The integer r is called the excessive index of G and denoted by . We set if an excessive factorization does not exist. Analogously, let m be a fixed positive integer. An excessivem]-factorization is a set M={M1,M2,…,Mk} of matchings of G, all of size m, whose union is E(G) and, subject to this condition, k is minimum. The integer k is denoted by and called the excessive m]-index of G. Again, we set if an excessive m]-factorization does not exist. In this paper we shall prove that, for bipartite multigraphs, both the parameters and are computable in polynomial time, and we shall obtain an efficient algorithm for finding an excessive factorization and excessive m]-factorization, respectively, of any bipartite multigraph. |
| |
Keywords: | Excessive factorization Bipartite multigraph Matching theory Network flow Vertex cover |
本文献已被 ScienceDirect 等数据库收录! |
|