We present improved partition refinement algorithms for three problems: lexicographic sorting, relational coarsest partition, and double lexical ordering. Our double lexical ordering algorithm uses a new, efficient method for unmerging two sorted sets.
R. Paige and R. E. Tarjan, "Three Partition Refinement Algorithms," SIAM Journal on Computing, Society for Industrial and Applied Mathematics (SIAM), Jan 1987.
The definitive version is available at https://doi.org/10.1137/0216062
Mathematics and Statistics
International Standard Serial Number (ISSN)
Article - Journal
© 1987 Society for Industrial and Applied Mathematics (SIAM), All rights reserved.