Applications of Matching in Bipartite Graph
| Main Author: | Wynn Swe |
|---|---|
| Format: | Article |
| Terbitan: |
, 2019
|
| Subjects: | |
| Online Access: |
https://zenodo.org/record/3545503 |
Daftar Isi:
- The aim of this work is to study lattice graphs which are readily seen to have many perfect matchings and considers application of matching in bipartite graph, such as the optimal assignment problem. Assignment problem is an important subject discussed in real physical world. We endeavor in this paper to introduce a new approach to assignment problem namely, ones assignment method, for solving a wide range of such problems. This method offers significant advantages over similar methods, in the process, first we define the assignment matrix, then by using determinant representation we obtain a reduced matrix which has at least one 1 in each row and column. Then by using the new method, we obtain an optimal solution for assignment problem by assigning ones to each row and each column. The new method is based on creating some ones in the assignment matrix and then try to find a complete assignment to there ones. The proposed method is a systematic procedure, easy to apply and can be utilized for all types of assignment problem with maximize or minimize objective functions. At the end, this method is illustrated with some numerical examples.