𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the complexity of interval orders and semiorders

✍ Scribed by U. Faigle; Gy. Turán

Publisher
Elsevier Science
Year
1987
Tongue
English
Weight
607 KB
Volume
63
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The recognition complexity of interval orders is shown to be Q(n log, n), and an optimal algorithm is given for the identification of semiorders. * Supported by the joint research project "Algorithmic Aspects of Combinatorial Optimization" of the Hungarian Academy of Sciences (Magyar Tudomanyos Akademia) and the German Research Association (Deutsche Forschungsgemeinschaft) and SFB 303 (DFG).

📜 SIMILAR VOLUMES

Aspects of semiorders within interval or
Aspects of semiorders within interval orders
✍ Peter C. Fishburn 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 791 KB

Let sk(n) be the largest integer such that every n-point interval order with NO antichain of more than k points includes an Sk(n)-point 'semiorder. When k = 1, s,(n) = n since all interval ordexs with no two-point antichains are ch:&s.