Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Optimal linear extensions by interchanging chains

Author: Ivan Rival
Journal: Proc. Amer. Math. Soc. 89 (1983), 387-394
MSC: Primary 06A10; Secondary 06A05, 90B35
MathSciNet review: 715851
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: For a finite ordered set $ P$ how can a linear extension $ L = {C_1} \oplus {C_2}$ be constructed which minimizes the number $ m$ of chains $ {C_i}$ of $ P$? While this question remains largely unanswered we show that a natural "greedy" algorithm is actually optimal for a far wider class of ordered sets than was hitherto suspected.

References [Enhancements On Off] (What's this?)

  • [G] Chaty and M Chein (1979), Ordered matchings and matchings without alternating cycles in bipartite graphs, Utilitas Math. 16, 183-187. MR 556990 (81e:05109)
  • [M] Chein and M. Habib (1980), The jump number of dags and posets: an introduction, Ann. Discrete Math. 9, 189-194. MR 597371 (81m:05071)
  • [O] Cogis (1982), Problem 4.6, Ordered Sets (I. Rival, ed.), Reidel, Dordrecht, p. 814. MR 661289 (83e:06003)
  • [O] Cogis and M. Habib (1979), Nombre de sauts et graphes série-parallèles, RAIRO Inform. Théor. 13, 3-18. MR 525454 (81h:05068)
  • [R] P. Dilworth (1950), A decomposition theorem for partially ordered sets, Ann. of Math. (2) 51, 161-166. MR 0032578 (11:309f)
  • [D] Duffus, I. Rival and P. Winkler (1982), Minimizing setups for cycle-free ordered sets, Proc. Amer. Math. Soc. 85, 509-513. MR 660592 (83m:06003)
  • [G] Gierz and W. Poguntke (1982), Minimizing setups for ordered sets: a linear algebraic approach, SIAM J. Algebraic Discrete Methods. MR 689874 (84d:06002)
  • [P] Grillet (1969), Maximal chains and antichains, Fund. Math. 65, 157-167. MR 0244112 (39:5429)
  • [B] Leclerc and B. Monjardet (1973), Orders "C.A.C.", Fund. Math. 79, 11-22. MR 0319823 (47:8364)
  • [W] R. Pulleyblank (1982), On minimizing setups in precedence constrained scheduling, Discrete Applied Math. E. Szpilrajn (1930), Sur l'extension de l'ordre partiel, Fund. Math. 16, 386-389.
  • [J] Valdes (1978), Parsing flowcharts and series-parallel graphs, Technical Report STAN-CS-78-682, Stanford.
  • [J] Valdes, R. E. Tarjan and E. L. Lawler (1982), The recognition of series-parallel digraphs, SIAM J. Comput. 11, 298-313. MR 652904 (84d:68073)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 06A10, 06A05, 90B35

Retrieve articles in all journals with MSC: 06A10, 06A05, 90B35

Additional Information

Keywords: Linear extension, chain decomposition
Article copyright: © Copyright 1983 American Mathematical Society

American Mathematical Society