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...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article NonPeerReviewed |
| Published: |
[Yogyakarta] : Universitas Gadjah Mada
2001
|
| Subjects: | |
| Online Access: | https://repository.ugm.ac.id/24734/ http://i-lib.ugm.ac.id/jurnal/download.php?dataId=7712 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Universitas Gadjah Mada |
| Summary: | 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 |
|---|