MASALAH PARTISI GRAF BOTTLENECK (BOTTLENECK GRAPH PARTITION PROBLEM)
ABSTRACT The Bottleneck graph partition problem is a partition of the vertices of an undirected edge weighted graph into two equally vertices sized sets, which are graph components, such that the maximum edge weight in the cut separing the two sets becomes minimum. In this thesis, the problem was so...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| التنسيق: | مقال NonPeerReviewed |
| منشور في: |
[Yogyakarta] : Universitas Gadjah Mada
2001
|
| الموضوعات: | |
| الوصول للمادة أونلاين: | https://repository.ugm.ac.id/24734/ http://i-lib.ugm.ac.id/jurnal/download.php?dataId=7712 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| المؤسسة: | Universitas Gadjah Mada |
| الملخص: | ABSTRACT
The Bottleneck graph partition problem is a partition of the vertices of an undirected edge weighted graph into two equally vertices sized sets, which are graph components, such that the maximum edge weight in the cut separing the two sets becomes minimum.
In this thesis, the problem was solved by an optimum algorithm with running time 0(m+n3logn), where n is the number of vertices and m is the number of edges in the graph.
This algorithm based on binary search tree using greedy method on prim's algorithm. On validation the random graph is used for the computer's program.
Keywords : graph partition, bottleneck, greedy method, prim's algorithm |
|---|