DMTCS Proceedings, 2005 International Conference on Analysis of Algorithms

Font Size:  Small  Medium  Large

Distribution-sensitive set multi-partitioning

Amr Elmasry


Given a set S with real-valued members, associated with each member one of two possible types; a multi-partitioning of S is a sequence of the members of S such that if x,y ∈S have different types and x<y, x precedes y in the multi-partitioning of S. We give two distribution-sensitive algorithms for the set multi-partitioning problem and a matching lower bound in the algebraic decision-tree model. One of the two algorithms can be made stable and can be implemented in place. We also give an output-sensitive algorithm for the problem.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional