PENENTUAN MATCHING MAKSIMUM PADA GRAF BIPARTIT BERBOBOT MENGGUNAKAN METODE HUNGARIAN
Matching is a part of graph theory that discuss to make a pair, that can be used to solve many problems; one of them is the assignment problem. The assignment problem is to make a pair problem for n as the employees and for n as the duties, therefore each employee gets one duty, and each duty is giv...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Muhammadiyah University Press
2012-06-01
|
| Series: | Jurnal Ilmiah Teknik Industri |
| Subjects: | |
| Online Access: | http://journals.ums.ac.id/index.php/jiti/article/view/984/678 |
| _version_ | 1818195338596450304 |
|---|---|
| author | Muchammad Abrori Rina Wahyuningsih |
| author_facet | Muchammad Abrori Rina Wahyuningsih |
| author_sort | Muchammad Abrori |
| collection | DOAJ |
| description | Matching is a part of graph theory that discuss to make a pair, that can be used to solve many problems; one of them is the assignment problem. The assignment problem is to make a pair problem for n as the employees and for n as the duties, therefore each employee gets one duty, and each duty is given exactly for each employee. The assignment problem can be solved by determining the matching in weighted bipartite graph through Hungarian Method. It can be determined from the alternating tree of a formed edge. If there is augmenting path, that augmenting path is used to form the more number of matching. If the formed path is alternating path, therefore the process is labeling the new node until finding the augmenting vertices. This matching is called as the perfect matching with the number of maximum weighed side in weighted bipartite graphs. The result matching is the solution for the assignment problem by giving an employee with a duty. |
| first_indexed | 2024-12-12T01:16:36Z |
| format | Article |
| id | doaj.art-8644e9c7488b4873b668239bc6ab12ab |
| institution | Directory Open Access Journal |
| issn | 1412-6869 2460-4038 |
| language | English |
| last_indexed | 2024-12-12T01:16:36Z |
| publishDate | 2012-06-01 |
| publisher | Muhammadiyah University Press |
| record_format | Article |
| series | Jurnal Ilmiah Teknik Industri |
| spelling | doaj.art-8644e9c7488b4873b668239bc6ab12ab2022-12-22T00:43:19ZengMuhammadiyah University PressJurnal Ilmiah Teknik Industri1412-68692460-40382012-06-01111921PENENTUAN MATCHING MAKSIMUM PADA GRAF BIPARTIT BERBOBOT MENGGUNAKAN METODE HUNGARIANMuchammad Abrori0Rina Wahyuningsih1Universitas Islam Negeri Sunan Kalijaga, JogjakartaUniversitas Islam Negeri Sunan Kalijaga, JogjakartaMatching is a part of graph theory that discuss to make a pair, that can be used to solve many problems; one of them is the assignment problem. The assignment problem is to make a pair problem for n as the employees and for n as the duties, therefore each employee gets one duty, and each duty is given exactly for each employee. The assignment problem can be solved by determining the matching in weighted bipartite graph through Hungarian Method. It can be determined from the alternating tree of a formed edge. If there is augmenting path, that augmenting path is used to form the more number of matching. If the formed path is alternating path, therefore the process is labeling the new node until finding the augmenting vertices. This matching is called as the perfect matching with the number of maximum weighed side in weighted bipartite graphs. The result matching is the solution for the assignment problem by giving an employee with a duty.http://journals.ums.ac.id/index.php/jiti/article/view/984/678matchinggraphassignment problemHungarian method |
| spellingShingle | Muchammad Abrori Rina Wahyuningsih PENENTUAN MATCHING MAKSIMUM PADA GRAF BIPARTIT BERBOBOT MENGGUNAKAN METODE HUNGARIAN Jurnal Ilmiah Teknik Industri matching graph assignment problem Hungarian method |
| title | PENENTUAN MATCHING MAKSIMUM PADA GRAF BIPARTIT BERBOBOT MENGGUNAKAN METODE HUNGARIAN |
| title_full | PENENTUAN MATCHING MAKSIMUM PADA GRAF BIPARTIT BERBOBOT MENGGUNAKAN METODE HUNGARIAN |
| title_fullStr | PENENTUAN MATCHING MAKSIMUM PADA GRAF BIPARTIT BERBOBOT MENGGUNAKAN METODE HUNGARIAN |
| title_full_unstemmed | PENENTUAN MATCHING MAKSIMUM PADA GRAF BIPARTIT BERBOBOT MENGGUNAKAN METODE HUNGARIAN |
| title_short | PENENTUAN MATCHING MAKSIMUM PADA GRAF BIPARTIT BERBOBOT MENGGUNAKAN METODE HUNGARIAN |
| title_sort | penentuan matching maksimum pada graf bipartit berbobot menggunakan metode hungarian |
| topic | matching graph assignment problem Hungarian method |
| url | http://journals.ums.ac.id/index.php/jiti/article/view/984/678 |
| work_keys_str_mv | AT muchammadabrori penentuanmatchingmaksimumpadagrafbipartitberbobotmenggunakanmetodehungarian AT rinawahyuningsih penentuanmatchingmaksimumpadagrafbipartitberbobotmenggunakanmetodehungarian |