Author name cluster

Mark R. Brown

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

STOC Conference 1978 Conference Paper

A Representation for Linear Lists with Movable Fingers

Mark R. Brown
Robert Endre Tarjan

This paper describes a data structure which is useful for representing linear lists when the pattern of accesses to a list exhibits a (perhaps time-varying) locality of reference. The structure has many of the properties of the representation proposed by Guibas, McCreight, Plass, and Roberts [4], but is substantially simpler and may be practical for lists of moderate size. The analysis of our structure includes a general treatment of the worst-case node splitting caused by consecutive insertions into a 2-3 tree.

Details

STOC Conference 1977 Conference Paper

The Complexity of Priority Queue Maintenance

Mark R. Brown

A notion of priority queue efficiency is defined, based on comparison counting. A good lower bound on the average and worst case number of comparisons is derived; several priority queue algorithms are exhibited which nearly attain the bound. It is shown that one of these algorithms, using binomial queues, can be characterized in a simple way based on the number and type of comparisons that it requires. The proof of this result involves an interesting problem on trees for which Huffman's construction gives a solution.

Details