Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331946 | Information Processing Letters | 2005 | 6 Pages |
Abstract
The k-MST is a well known NP-hard problem and several approximation algorithms exist to solve this problem with a guaranteed performance bound. A closely related problem, called the bottleneck k-MST (BMST(k)) can however be solved in O(mlogn) time on graph with n nodes and m edges. We propose two algorithms to solve BMST(k), one of complexity O(m+nlogn) and the other of O(m) time. We also consider a generalization of BMST(k) which subsumes many bottleneck problems studied in the literature and show that this generalized problem can also be solved in O(m) time.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Abraham P. Punnen, Olena Chapovska,