This reseearch will investigate the minimum spanning tree and matching problems from the point of view of inherent complexity. The best known algorithms for both problems use priority queues in similar ways. The priority queue operations are the bottlenecks of these algorithms. By investigating the inherent complexity of the priority queue problems in the comparison tree model, it should be possible to determine how far current ideas about how to solve these problems can be pushed.
