Optimal linear extensions by interchanging chains

Rival, Ivan

doi:10.1090/S0002-9939-1983-0715851-3

Optimal linear extensions by interchanging chains
HTML articles powered by AMS MathViewer

by Ivan Rival PDF

Proc. Amer. Math. Soc. 89 (1983), 387-394 Request permission

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

G. Chaty and M. Chein, Ordered matching and matchings without alternating cycles in bipartite graphs, Utilitas Math. 16 (1979), 183–187. MR 556990
M. Chein and M. Habib, The jump number of dags and posets: an introduction, Ann. Discrete Math. 9 (1980), 189–194. MR 597371, DOI 10.1017/s0001867800043305
Ivan Rival (ed.), Ordered sets, NATO Advanced Study Institute Series C: Mathematical and Physical Sciences, vol. 83, D. Reidel Publishing Co., Dordrecht-Boston, Mass., 1982. MR 661289
O. Cogis and M. Habib, Nombre de sauts et graphes série-parallèles, RAIRO Inform. Théor. 13 (1979), no. 1, 3–18, ii (French, with English summary). MR 525454, DOI 10.1051/ita/1979130100031
R. P. Dilworth, A decomposition theorem for partially ordered sets, Ann. of Math. (2) 51 (1950), 161–166. MR 32578, DOI 10.2307/1969503
D. Duffus, I. Rival, and P. Winkler, Minimizing setups for cycle-free ordered sets, Proc. Amer. Math. Soc. 85 (1982), no. 4, 509–513. MR 660592, DOI 10.1090/S0002-9939-1982-0660592-3
Gerhard Gierz and Werner Poguntke, Minimizing setups for ordered sets: a linear algebraic approach, SIAM J. Algebraic Discrete Methods 4 (1983), no. 1, 132–144. MR 689874, DOI 10.1137/0604016
P. A. Grillet, Maximal chains and antichains, Fund. Math. 65 (1969), 157–167. MR 244112, DOI 10.4064/fm-65-2-157-167
B. Leclerc and B. Monjardet, Ordres “C. A. C.”, Fund. Math. 79 (1973), no. 1, 11–22 (French). MR 319823, DOI 10.4064/fm-79-1-11-22

On minimizing setups in precedence constrained scheduling

Sur l’extension de l’ordre partiel

16

Parsing flowcharts and series-parallel graphs

Jacobo Valdes, Robert E. Tarjan, and Eugene L. Lawler, The recognition of series parallel digraphs, SIAM J. Comput. 11 (1982), no. 2, 298–313. MR 652904, DOI 10.1137/0211023