Detail Inovasi Perguruan Tinggi


Tema: Teknik Elektro
Judul: On Weighted Component Edge Connectivity of Trees and Unicycles
Perguruan Tinggi: Universitas Presiden
Jenis/sdm: dosen/0408055403

Tahun: 2010

Let G be a graph with n nodes and e edges and suppose each node is assigned a positive integer weight. Set W to be the sum of the weights of the nodes of G and w ¯ to be the maximum weight assigned to any node. Given k such that w ¯<k≤W, the weighted component edge connectivity of a graph is the minimum number of edges that must be removed from the graph so that each component of the resulting subgraph has weight no greater than k-1.We present an efficient algorithm for determining the value of this parameter for trees and unicycles and give some computational consequences of the algorithm.