The Cost of Cache-Oblivious Searching Michael A. Bender (2008)
Gerth Sto/lting Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, John Iacono
zx
Improved Bounds on Sorting by Length-Weighted Reversals ∗ (2008)
Michael A. Bender, Dongdong Ge, Simai He, Haodong Hu, Ron Y. Pinter, Steven Skiena, ...
We study the problem of sorting binary sequences and permutations by length-weighted reversals. We consider a wide class of cost functions, namely f(ℓ) = ℓ α for all α ≥ 0, where ℓ is the...
An Adaptive Packed-Memory Array (2008)
The packed-memory array (PMA) is a data structure that maintains a dynamic set of N elements in sorted order in a Θ(N)-sized array. The idea is to intersperse Θ(N) empty spaces or gaps among the...
Sorting by length-weighted reversals: Dealing with signs and circularity (2004)
Firas Swidan, Michael A. Bender, Dongdong Ge, Simai He, Haodong Hu, Ron Y. Pinter
Abstract. We consider the problem of sorting linear and circular permutations and 0/1 sequences by reversals in a length-sensitive cost model. We extend the results on sorting by length-weighted...
Improved Bounds on Sorting with Length-Weighted Reversals (Extended Abstract) (2004)
Michael A. Bender, Dongdong Ge, Simai He, Haodong Hu, Ron Y. Pinter, Steven Skiena, ...
Michael A. Bender y Dongdong Ge Simai He Haodong Hu Ron Y. Pinter Steven Skiena Firas Swidan Abstract We study the problem of sorting integer sequences and permutations by length-weighted reversals....
Sorting by length-weighted reversals: Dealing with signs and circularity (2004)
Firas Swidan, Michael A. Bender, Dongdong Ge, Simai He, Haodong Hu, Ron Y. Pinter
Abstract. We consider the problem of sorting linear and circular permutations and 0/1 sequences by reversals in a length-sensitive cost model. We extend the results on sorting by length-weighted...
The Cost of Cache-Oblivious Searching (2003)
Michael A. Bender, Gerth Stølting Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, ...
Tight bounds on the cost of cache-oblivious searching are proved. It is shown that no cache-oblivious search structure can guarantee that a search performs fewer than lg e log B N block transfers...