I've been looking for the work on persistent real-time catenable deques. There are various approaches that have logarithmic complexities for concatenation of deques, and some that have amortized constant-time implementation, but much fewer real-time (non-amortized) deques with constant-time concatenation.
The well-known real-time catenable deque is the one described in the 1999 article by Haim Kaplan and Robert Tarjan, Purely Functional, Real-Time Deques with Catenation. However, both the wikipedia page on deques and this fantastic StackOverflow answer mention more recent work (apparently 2003) by Robert Tarjan and Radu Mihaescu, that is supposedly simpler.
Does anyone have a link to a publication by Robert Tarjan and Mihaescu on this work? The only thing I could find while browsing the web is a .doc document, apparently a part of some course notes, and that format is neither comfortable to read nor maybe reliable enough to base an implementation on.
Some web pages refer to the second author as "Mihaesau", which seems to be a mistake. I found a DBLP list of publications, more recent and not mentioning catenable queues, and a meager webpage, with no links to a publication section.
A great answer on CStheory.SE links to that .doc
and states that
So apparently there's no conference or journal description of the data structure and you've already got the definitive reference, until now at least. Note that the course is question is given by Tarjan. You could inquire by email about this data structure.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With