Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Where is the "*simpler* real-time catenable deque" work of Tarjan and Mihaescu?

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.

like image 292
gasche Avatar asked May 07 '13 15:05

gasche


1 Answers

A great answer on CStheory.SE links to that .doc and states that

  • The most recent version of Kaplan & Tarjan's work was published in 2000. This version is simpler in some ways.

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.

like image 149
Fred Foo Avatar answered Nov 16 '22 01:11

Fred Foo