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.