×

zbMATH — the first resource for mathematics

On some complexity properties of N-free posets and posets with bounded decomposition diameter. (English) Zbl 0608.06004
Among generalizations of series-parallel posets, the N-free posets are much better known than posets with bounded decomposition diameter, i.e., those posets iteratively built up by substitution from posets of cardinality at most k. Nevertheless, the authors demonstrate that the latter class may well be the better one for a variety of combinatorial optimization problems and other reasons. Thus, although the jump-number problem is shown to be polynomially solvable on both classes, the isomorphism problem and the 1/prec/\(\sum w_ jC_ j\) scheduling problem are here demonstrated to be among these which are only polynomially solvable for the second class. As an early exponent of the merits of the substitution technique, this author finds the success of the method more than only interesting. Since the subject is still in a process of evolving its main outlines, this paper will make an important difference in the direction of eventual development. To the extent that it will be superseded by further results, its very success will make its view more commonplace.

MSC:
06A06 Partial orders, general
05A05 Permutations, words, matrices
90B35 Deterministic scheduling theory in operations research
06B25 Free lattices, projective lattices, word problems
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading · Zbl 0286.68029
[2] Bern, M.W.; Lawler, E.L.; Wong, A.L., Linear time computation of optimal subgraphs of decomposable graphs, (1985), preprint · Zbl 0618.68058
[3] Booth, K.S.; Colbourn, C.J., Problems polynomially equivalent to graph isomorphism, CS-77-04, (1979), University of Waterloo
[4] Buer, H.; Möhring, R.H., A fast algorithm for the decomposition of graphs and posets, Math. oper. res., 8, 170-184, (1983) · Zbl 0517.05057
[5] Chaty, G.; Chein, M.; Martin, P.; Petolla, G., Some results about the jump number of an acircuit digraph, Utilitas math., 267-279, (1974), Proc. 5th S-E Conf. Combinatorics, Graph Theory and Computing, BocaRaton, Feb. 1973, Congressus Numerantium X
[6] Chein, M.; Habib, M., The jump number of dags and posets: an introduction, Ann. discrete math., 9, 189-194, (1980) · Zbl 0445.05048
[7] Cogis, O.; Habib, M., Nombre de sauts et graphes série-paralléles, R.A.I.R.O. informatique théorique⧸theorical informatics, Vol 13, No. 1, 3-18, (1979) · Zbl 0413.05013
[8] Corneil, D.G.; Lerchs, H.; Stewart Burlingam, L., Complement reducible graphs, Discrete appl. math., 3, 163-174, (1981) · Zbl 0463.05057
[9] Duffin, R.J., Topology of series-parallel networks, J. math. analysis appl., 10, 303-318, (1965) · Zbl 0128.37002
[10] Dushnik, B.; Miller, E.W., Partially ordered sets, Amer. J. math., 63, 600-610, (1941) · Zbl 0025.31002
[11] Faigle, U.; Gierz, G., A construction for strongly greedy ordered sets, (), 307-314
[12] Gierz, G.; Poguntke, W., Minimizing setups for ordered sets: a linear algebraic approach, SIAM J. algebraic discrete methods, 4, 132-144, (1983) · Zbl 0517.06004
[13] Grillet, P.A., Maximal chains and antichains, Fund. math., 65, 157-167, (1969) · Zbl 0191.00601
[14] Habib, M., Substitutions des structures combinatories: théorie et algothmes, Thése science université P. et M. Curie, (1981), Paris VI
[15] Habib, M., Comparability invariants, Ann. discrete math., 23, 371-386, (1984)
[16] Habib, M.; Jegou, R., N-free posets as generalizations of series-parallel posets, Discrete appl. math., 12, 3, 279-291, (1985) · Zbl 0635.06002
[17] Habib, M.; Maurer, M.C., On the X-join decomposition for undirected graphs, Discrete appl. math., 1, 201-207, (1979) · Zbl 0439.05041
[18] Hemminger, R.L.; Beineke, L.W., Line graphs and line diagraphs, (), 271-305
[19] Heuchenne, C., Sur une certaine correspondance entre graphes, Bull. soc. roy. sci. liége, 33, 743-753, (1964) · Zbl 0134.43302
[20] Hopcroft, J.E.; Tarjan, R.E., Isomorphism of planar graphs, (), 131-152 · Zbl 0274.05103
[21] Kelly, D.; Trotter, W.T., Dimension theory for ordered sets, (), 171-211, Nato Advanced Studies
[22] Kleitman, D.J.; Rothschild, B.L., Asymptotic enumeration of partial orders on a finite set, Trans. amer. math. soc., 205, 205-220, (1975) · Zbl 0302.05007
[23] Knuth, D.E.; Szwarcfiter, J.L., A structured program to generate all topological sorting arrangements, Inform. proc. letters, 2, 153-157, (1974) · Zbl 0276.68026
[24] Lawler, E.L., Graphical algorithms and their complexity, Math. centre tracts, 81, 3-32, (1976) · Zbl 0358.68059
[25] Lawler, E.L., Sequencing jobs to minimize total weighted completion time subject to procedence constraints, Ann. discrete math., 2, 75-90, (1978) · Zbl 0374.68033
[26] Lawler, E.L.; Lenstra, J.K.; Rinnoy Kan, A.G., Recent developments in deterministic and stochastic scheduling, (), 35-73
[27] Leclerc, B.; Monjardet, B., Orders CAC, Fund. math., 11-22, (1973)
[28] Möhring, R.H., Almost all comparability graphs are UPO, Discrete math., 50, 63-70, (1984) · Zbl 0543.05054
[29] Möhring, R.H., Algorithmic aspects of comparability graphs and interval graphs, (), 41-101
[30] Möhring, R.H.; Radermacher, F.J., Substitution decomposition for discrete structures and connections with combinatorial optimization, Ann. discrete math., 19, 257-356, (1984) · Zbl 0567.90073
[31] Möhring, R.H.; Radermacher, F.J., Generalized results on the polynomiality of certain weighted sum scheduling problems, Methods oper. res., 49, 405-417, (1985) · Zbl 0561.90049
[32] Monma, C.L.; Sidney, J.B., Optimal sequencing via modular decomposition of sequencing functions, (1984), preprint · Zbl 0622.90050
[33] Muller, J.H.; Spinrad, J., On-line modular decomposition, Technical report GIT-ICS-84/11, (1984), Georgia Institute of Technology Atlanta
[34] W.H. Pulleyblank, On minimizing setups in precedence constrained scheduling problems, Discrete Appl. Math., to appear.
[35] Rival, I., Optimal linear extensions by interchanging chains, Proc. amer. math. soc., Vol. 85, No 4, 509-513, (1982)
[36] Rival, I., Linear extensions of finite ordered sets, Ann. discrete math., 23, 355-370, (1984)
[37] Rival, I.; Zaguia, N., Constructing N-free, Jump-critical ordered sets, (1985), preprint
[38] Saks, M., Problem session 1: on enumeration, (), 524
[39] Schnitzler, M., Untersuchungen zur komplexität des graphenisomorphie-problems mit hilfe von graph-grammatiken, Thesis RWTH Aachen, (1982)
[40] Sidney, J.B., Decomposition algorithms for single-machine sequencing with precedence relations and defferal cost, Oper. res., 23, 283-298, (1975) · Zbl 0304.90058
[41] Sidney, J.B.; Steiner, G., Optimal sequencing by modular decomposition: polynomial algorithms, Working paper 85-9, (1985), Faculty of Administration, University of Ottawa
[42] Steiner, G., On a decomposition algorithm for sequencing problems with precedence constraints, Report no 213, (1983), Faculty of Business, McMaster University Hamilton Canada
[43] Syslo, M.M., A labelling algorithm to recognize a line digraph and output its root digraph, Inform. proc. letters, 15, 28-30, (1982) · Zbl 0483.68062
[44] Syslo, M.M., Minimizing the jump number for ordered sets: a graph theoretic approach, Order 1, 7-19, (1984) · Zbl 0564.06001
[45] Syslo, M.M., A graph theoretic approach to the jump number problem, (), 185-215
[46] Takamizawa, K.; Nishizeki, T.; Saito, N., Linear-time computability of combinatorial problems on series-parallel graphs, JACM Vol. 29, No 3, 623-641, (1982) · Zbl 0485.68055
[47] Valdes, J., Parsing flowcharts and series-parallel graphs, Technical report STAN-CS-78-682, (1978), Computer Science Department Stanford, Ca
[48] Valdes, J.; Tarjan, R.E.; Lawler, E.L., The recognition of series-parallel digraphs, Proc. 11th ann. ACM symp. on theory of computing, 1-12, (1979)
[49] Yannakakis, M., The complexity of the partial order dimension problem, SIAM J. algebraic and discrete methods, Vol. 3, No 3, 351-358, (1982) · Zbl 0516.06001
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.