THREE PARTITION REFINEMENT ALGORITHMS.

Robert Paige; Robert E. Tarjan

doi:10.1137/0216062

THREE PARTITION REFINEMENT ALGORITHMS.

Robert Paige, Robert E. Tarjan

Research output: Contribution to journal › Article › peer-review

914 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	973-989
Number of pages	17
Journal	SIAM Journal on Computing
Volume	16
Issue number	6
DOIs	https://doi.org/10.1137/0216062
State	Published - 1987
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science
General Mathematics

Access to Document

10.1137/0216062

Cite this

@article{004cca2049aa4577a10c12a6070283da,

title = "THREE PARTITION REFINEMENT ALGORITHMS.",

abstract = "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.",

author = "Robert Paige and Tarjan, {Robert E.}",

year = "1987",

doi = "10.1137/0216062",

language = "English (US)",

volume = "16",

pages = "973--989",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "6",

}

TY - JOUR

T1 - THREE PARTITION REFINEMENT ALGORITHMS.

AU - Paige, Robert

AU - Tarjan, Robert E.

PY - 1987

Y1 - 1987

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0023566630&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023566630&partnerID=8YFLogxK

U2 - 10.1137/0216062

DO - 10.1137/0216062

M3 - Article

AN - SCOPUS:0023566630

SN - 0097-5397

VL - 16

SP - 973

EP - 989

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 6

ER -

THREE PARTITION REFINEMENT ALGORITHMS.

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this