algorithm - Tarjan 和 Mihaescu 的 "*simpler* real-time catenable deque"工作在哪里？

Question

我一直在寻找有关持久实时可链接双端队列的工作。有多种方法对双端队列的连接具有对数复杂性，有些方法具有摊销的恒定时间实现，但具有恒定时间连接的实时(非摊销)双端队列要少得多。

著名的实时可连接双端队列是 Haim Kaplan 和 Robert Tarjan 在 1999 年的文章中描述的，Purely Functional, Real-Time Deques with Catenation .然而，wikipedia page关于双端队列和 this fantastic StackOverflow answer提到 Robert Tarjan 和 Radu Mihaescu 最近的工作(显然是 2003 年)，这应该更简单。

有没有人有指向 Robert Tarjan 和 Mihaescu 关于这项工作的出版物的链接？我在浏览网页时唯一能找到的是 a .doc document ，显然是一些类(class)笔记的一部分，而且这种格式既不便于阅读，也不可能可靠到足以作为实现的基础。

有些网页将第二作者称为“Mihaesau”，这似乎是一个错误。我找到了一个 DBLP list of publications ，最近并没有提到可连接的队列，以及一个 meager webpage ，没有指向发布部分的链接。

Answer 1

A great answer on CStheory.SE链接到那个 .doc 并指出

• most recent version of Kaplan & Tarjan's work was published in 2000 .这个版本在某些方面更简单。

很明显，没有关于数据结构的 session 或期刊描述，而且您已经获得了权威引用，至少到现在为止是这样。请注意，这门类(class)的问题是由 Tarjan 给出的。您可以通过电子邮件查询此数据结构。