×
Habib, M.; Jegou, R.

N-free posets as generalizations of series-parallel posets. (English) Zbl 0635.06002

Discrete Appl. Math. 12, 279-291 (1985).
Summary: N-free posets have recently taken some importance and motivated many studies. This class of posets introduced by P. Grillet [Fund. Math. 65, 157-167 (1969; Zbl 0191.006)] and C. Heuchenne [Bull. Soc. Roy. Sci. Liège 33, 743-753 (1964; Zbl 0134.433)] is closely related to another important class of posets, namely the series-parallel posets, introduced by E. L. Lawler [Ann. Discrete Math. 2, 75-90 (1978; Zbl 0374.68033)] and studied by J. Valdes, R. E. Tarjan and E. L. Lawler [SIAM J. Comput. 11, 298-313 (1982; Zbl 0478.68065)]. This paper shows how N-free posets can be considered as generalizations of series-parallel posets, by giving a recursive construction of N-free posets. Furthermore we propose a linear time algorithm to recognize and decompose any N-free poset. This yields some very natural problems, namely: which are the properties (such as linear time algorithm for some invariant) of series-parallel posets that are kept for N-free posets?

Cited in 1 Review
Cited in 19 Documents

MSC:

06A06 Partial orders, general
05C99 Graph theory

Keywords:

N-free posets; series-parallel posets; algorithm

Citations:

Zbl 0191.006; Zbl 0134.433; Zbl 0374.68033; Zbl 0478.68065
Cite Review PDF
Full Text: DOI

References:

[1] Chein, M.; Habib, M., The jump number of dags and posets: an introduction, Ann. Discrete Math., 9, 189-194 (1980) · Zbl 0445.05048
[2] Cogis, O.; Habib, M., Nombre de sauts et graphes série-parrallèles, RAIRO Inform. Théor., 13, 1, 3-18 (1979) · Zbl 0413.05013
[3] Cunningham, W. H., Decomposition of directed graphs, SIAM J. Algebraic Discrete Methods, 3, 2, 214-228 (1982) · Zbl 0497.05031
[4] Cunningham, W. H.; Edmonds, J., A combinatorial decomposition theory, Canad. J. Math., 32, 734-765 (1980) · Zbl 0442.05054
[5] Duffin, R. J., Topology of series-parallel networks, J. Math. Analysis Appl., 10, 303-318 (1965) · Zbl 0128.37002
[6] Dushnik, B.; Miller, E. W., Partially ordered sets, Amer. J. Math., 63, 600-610 (1941) · Zbl 0025.31002
[7] Gierz, G.; Poguntke, W., Minimizing setups for ordered sets: a linear algebraic approach, SIAM J. Algebraic Discrete Methods, 4, 1, 132-144 (1983) · Zbl 0517.06004
[8] Grillet, P. A., Maximal chains and antichains, Fund. Math., 65, 157-167 (1969) · Zbl 0191.00601
[9] Habib, M.; Mohring, R., On some complexity properties of N-free posets (1985), Preprint · Zbl 0608.06004
[10] Hemminger, R. L.; Beineke, L. W., (Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory (1978), Academic Press: Academic Press London), 271-305 · Zbl 0423.00003
[11] Heuchenne, C., Sur une certaine correspondence entre graphes, Bull. Soc. Roy. Sci. Liège, 33, 743-753 (1964) · Zbl 0134.43302
[12] Lawler, E. L., Sequencing jobs to minimize total weighted completion time subject to precedence constraints, Ann. Discrete Math., 2, 75-90 (1978) · Zbl 0374.68033
[13] Leclerc, B.; Monjardet, B., Orders C.A.C., Fund. Math., 11-22 (1973) · Zbl 0356.06009
[14] Kelly, D.; Trotter, W. T., Dimension theory for ordered sets, (Rival, I., Ordered Sets. Ordered Sets, Nato Advanced Studies (1982)), 171-211 · Zbl 0499.06003
[15] W.R. Pulleyblank, On minimizing setups in precedence constrained scheduling, Discrete Appl. Math., to appear.; W.R. Pulleyblank, On minimizing setups in precedence constrained scheduling, Discrete Appl. Math., to appear.
[16] Rival, I., Optimal linear extensions by interchanging chains, (Proc. Amer. Soc., 85 (1982)), 509-513, 4
[17] Rival, I., Linear extensions of finite ordered sets, Ann. Discrete Math., 355-370 (1984) · Zbl 0551.06003
[18] Syslo, M. M., A labelling algorithm to recognize a line digraph and output its root digraph, Inform. Process. Lett., 15, 28-30 (1982) · Zbl 0483.68062
[19] Sysle, M. M., Minimizing the jump number for ordered sets: a graph-theoretic approach, Order 1, 7-19 (1984) · Zbl 0564.06001
[20] Takamizawa, K.; Nishizeki, T.; Saito, N., Linear-time computability of combinatorial problems on series-parallel graphs, J. ACM, 29, 3, 623-641 (1982) · Zbl 0485.68055
[21] Valdes, J.; Tarjan, R. E.; Lawler, E. L., The recognition of series-parallel digraphs, (Proc. 11th Ann. ACM Symp. on Theory of Computing (1979)), 1-12
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.