Research Initiation: Inherent Complexity of Priority Problems

本研究将从内在复杂性的角度来研究最小生成树和匹配问题。解决这两个问题的最著名的算法以相似的方式使用优先级队列。优先级队列操作是这些算法的瓶颈。通过调查比较树模型中优先级队列问题的内在复杂性，应该可以确定当前关于如何解决这些问题的想法可以推进到什么程度。

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.