SpringerLink
Log in

Computationally Tractable Classes of Ordered Sets

  • Chapter
Algorithms and Order

Part of the book series: NATO ASI Series ((ASIC,volume 255))

  • 369 Accesses

Abstract

Ordered sets have recently gained much importance in many applied and theoretical problems in computer science and operations research ranging from project planning via processor scheduling to sorting and retrieval problems. These problems involve partial orders as their basic structure, e.g. as precedence constraints in scheduling problems, or as comparability relation among the objects to be sorted or retrieved.

Since many of the involved problems are N P-hard in general, much attention has recently been given to special classes of partial orders with “nice” structural properties that lend themselves the design of efficient methods, and for obtaining bounds by structural relaxation in more general situations. Typical such classes are: series parallel partial orders, N-free partial orders, interval orders, two-dimensional partial orders, and partial orders with special decomposition properties.

This area of “computationally tractable” classes of partial orders shows many similarities and interactions with algorithmic graph theory and certain classes of perfect graphs.

We will present the structural properties of the mentioned classes, discuss their mutual relationship, and the algorithmic complexity of their recognition. In addition, we present the tractibility of these different classes on several applications dealing with scheduling and sorting.

Supported by Sonderforschungsbereich 303 (DFG), Institut für Operations Research, Universität Bonn, W. Germany

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (Thailand)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 330.63
Price includes VAT (Thailand)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 399.99
Price excludes VAT (Thailand)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info
Hardcover Book
EUR 399.99
Price excludes VAT (Thailand)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. A.V. Aho, M.R. Garey and J.D. Ullman (1972) ‘The transitive reduction of a directed graph’, SIAM J. Comput. 1, 131–137

    MathSciNet  MATH  Google Scholar 

  2. A.V. Aho, J.E. Hopcroft and J.D. Ullman (1975) The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Ma.

    Google Scholar 

  3. M.D. Atkinson (1989) ‘The complexity of orders’, this volume

    Google Scholar 

  4. M.D. Atkinson and H.W. Chang (1986) ‘Extensions of partial orders of bounded width’, Congressus Num. 52, 21–35

    MathSciNet  Google Scholar 

  5. K.A. Baker, P.C. Fishburn and F.S. Roberts (1971) ‘Partial orders of dimension 2’ Networks 2, 11–28

    MathSciNet  Google Scholar 

  6. J.P. Barthèlemy, C. Flambert and B. Monjardet (1982) ‘Ordered sets and social sciences’, in [Ri2], 721–758

    Google Scholar 

  7. M. Bartusch, R.H. Möhring and F.J. Radermacher (1987) M-machine unit time scheduling: a report on ongoing research, preprint

    Google Scholar 

  8. M. Bartusch, R.H. Möhring and F.J. Radermacher (1987) ‘Scheduling project networks with resource constraints and time windows’, to appear in Annals of Oper. Res.

    Google Scholar 

  9. C. Benzaken, P.L. Hammer and D. de Werra (1985) ‘Split graphs of Dilworth number 2’, Discrete Math. 55,123–128

    MathSciNet  MATH  Google Scholar 

  10. K.P. Bogart (1982) ‘Some social science applications of ordered sets’, in [Ri2], 759–787

    Google Scholar 

  11. B. Bollobás and P. Hell (1985) ‘Sorting and graphs’, in [Ri3], 169–184

    Google Scholar 

  12. S. Booth and S. Lueker (1976) ‘Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms’, J. Comput. Syst. Sci. 13, 335–379

    MathSciNet  MATH  Google Scholar 

  13. V. Bouchittè and M. Habib (1989) ‘The calculation of invariants’, this volume

    Google Scholar 

  14. G. Boudol and I. Castellani (1986) ‘On the semantics of concurrency: partial orders and transition systems’, preprint, INRIA, 06560-Valbonne, France

    Google Scholar 

  15. A. Brandständt and D. Kratsch (1984) ‘On the restriction of some JVP-complete graph problems to permutation graphs’, Report No. N/84/80, Friedrich-Schiller Universität Jena, German Democratic Republic

    Google Scholar 

  16. A. Brandständt and D. Kratsch (1986) ‘On partitions of permutations into increasing and decreasing subsequences’, J. Inform. Processing and Cybernetics (EIK) 22, 263–273

    Google Scholar 

  17. H. Buer and R.H. Möhring (1983) ‘A fast algorithm for the decomposition of graphs and posets’, Math. Oper. Res. 8, 170–184

    MathSciNet  MATH  Google Scholar 

  18. G. Chaty, M. Chein, P. Martin, G. Potella (1976) ‘Some results about the jump number of jumps in aircuit digraphs’, Proc. 5 t h Conf. Combinatorics, Graph Theory and Computing, Utilitas Math. 267–279

    Google Scholar 

  19. M. Chein and M. Habib (1980) The jump number of dags and posets: an introduction’, Ann. of Discrete Math. 9, 189–194

    MathSciNet  MATH  Google Scholar 

  20. V. Chvatal and P.L. Hammer (1977) ‘Aggregation of inequalities in integer programming’, Annals Discrete Math. 1, 145–162

    MathSciNet  Google Scholar 

  21. E.G. Coffman, Jr. and R.L. Graham (1972): ‘Optimal scheduling for two-processor systems’. Acta Informatica 1, 200–213

    MathSciNet  Google Scholar 

  22. D.G. Cornell, H. Lerchs and L. Stewart Burlingham (1981) ‘Complement reducible graphs’, Discr. Appl. Math. 3, 163–174

    Google Scholar 

  23. D.G. Cornell, Y. Perl and L. Stewart (1985) ‘A linear recognition algorithm for cographs’, SIAM J. Comput. 14, 926–934

    MathSciNet  Google Scholar 

  24. C.J. Colbourn (1981) On testing isomorphism of permutation graphs’, Networks 11, 13–21

    MathSciNet  MATH  Google Scholar 

  25. C.J. Colbourn and W.R. Pulleyblank (1985) ‘Minimizing setups in ordered sets of fixed width’, Order 1, 225–228

    MathSciNet  MATH  Google Scholar 

  26. U. Derigs, O. Goecke, and R. Goecke (1984) ‘Bisimplicial edges, Gaussian elimination and matchings in bipartite graphs’, Proc. Int. Workshop on Graphtheoretic Concepts in Computer Science, Trauner Verlag, Berlin, W. Germany, 79–87

    Google Scholar 

  27. R.J. Duffin (1965) ‘Topology of series-parallel networks’, J. Math. Analysis Appl. 10, 303–318

    MathSciNet  MATH  Google Scholar 

  28. B. Dushnik and E. Miller (1941) ‘Partially ordered sets’, Amer. J. Math. 63, 600–610

    MathSciNet  Google Scholar 

  29. S.E. Elmaghraby (1977) Activity Networks, Wiley, New York

    MATH  Google Scholar 

  30. M. El-Zahar (1989) this volume

    Google Scholar 

  31. U. Faigle, G. Gierz and R. Schrader (1985) ‘Algorithmic approaches to setup minimization’, SIAM J. Comput. 14, 954–965

    MathSciNet  MATH  Google Scholar 

  32. U. Faigle, L. Lovász, R. Schrader and Gy. Turan (1986) ‘Searching in trees, series-parallel and interval orders’, SIAM J. Comput. 15, 1075–1084

    MathSciNet  MATH  Google Scholar 

  33. U. Faigle and R. Schrader (1985) ‘A setup heuristic for interval orders’, Oper. Res. Letters 4, 185–188

    MathSciNet  MATH  Google Scholar 

  34. U. Faigle and R. Schrader (1986) ‘On the computational complexity of the order polynomial’, Discrete Appl. Math. 15, 261–269

    MathSciNet  MATH  Google Scholar 

  35. U. Faigle and R. Schrader (1987) private communication

    Google Scholar 

  36. P.C. Fishburn (1970) ‘Intransitive indifference in preference theory: A survey’, Oper. Res. 18, 207–228

    MathSciNet  MATH  Google Scholar 

  37. P.C. Fishburn (1985) Interval orders and Interval Graphs, Wiley, New York

    MATH  Google Scholar 

  38. P.C. Fishburn (1985) ‘Interval graphs and interval orders’, Discrete Math. 55, 135–150

    MathSciNet  MATH  Google Scholar 

  39. P.C. Fishburn, W.V. Gehrlein (1986) ‘Minimizing bumps in linear extensions of ordered sets’, Order 3, 3–14

    MathSciNet  MATH  Google Scholar 

  40. L.R. Ford and D.R. Fulkerson (1962) Flows in Networks, Princeton Univ. Press, Princeton, New Jersey

    Google Scholar 

  41. D.J. Foulis (1970) Empirical logic, Course Notes, Univ. of Massechusetts

    Google Scholar 

  42. D.R. Fulkerson and O.A. Gross (1965) ‘Incidence matrices and interval graphs’, Pacific J. Math. 15, 835–855

    MathSciNet  MATH  Google Scholar 

  43. H.N. Gabov (1982) ‘An almost-linear algorithm for two-processor scheduling’, J.ACM 29, 766–780

    Google Scholar 

  44. T. Gallai (1967) ‘Transitiv orientierbare Graphen’, Acta Math. Acad. Scient Hung. Tom. 18, 25–66

    MathSciNet  MATH  Google Scholar 

  45. M.R. Garey and D.S. Johnson (1979) Computers and Intractability: A Guide to the Theory of Ν Ρ-Completeness, Freeman, San Francisco

    Google Scholar 

  46. M.R. Garey, D.S. Johnson, R.E. Tarjan and M. Yannakakis (1983) ‘Scheduling opposing forests’, SIAM J. Alg. Disc. Meth. 4, 72–93

    MathSciNet  MATH  Google Scholar 

  47. P.C. Gilmore and A.J. Hoffman (1964) ‘A characterization of comparability graphs and of interval graphs’, Canad. J. Math. 16, 539–548

    MathSciNet  MATH  Google Scholar 

  48. J.L. Gischer (1984) Partial orders and the axiomatic theory of shuffle, Thesis, Stanford University

    Google Scholar 

  49. M.C. Golumbic (1980) Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York

    MATH  Google Scholar 

  50. M.C. Golumbic (1985) ‘Interval graphs and related topics’, Discrete Math. 55, 113–121

    MathSciNet  MATH  Google Scholar 

  51. S. Goto and T. Matsuda (1986) ‘Partitioning, assignment and placement’, in T. Ohtsuki (ed.) Layout Design and Verification, North Holland, Amsterdam, 55–98

    Google Scholar 

  52. P. Grillet (1969) ‘Maximal chains and antichains’, Fund. Math. 65, 157–167

    MathSciNet  MATH  Google Scholar 

  53. M. Habib (1984) ‘Comparability invariants’, Annals Discrete Math., 23 331–386

    Google Scholar 

  54. M. Habib and R. Jegou (1985) ‘N-free posets as generalizations of series-parallel posets’, Discrete Appl. Math. 12 (3), 279–291

    MathSciNet  MATH  Google Scholar 

  55. M. Habib and M.C. Maurer (1979) ‘On the X-join decomposition for undirected graphs’, Appl. Discr. Math. 3, 198–207

    Google Scholar 

  56. M. Habib and R.H. Möhring (1987) ‘On some complexity properties of N-free posete and posets with bounded decomposition diameter’, Discrete Math. 63, 157–182

    MathSciNet  MATH  Google Scholar 

  57. M. Habib, R.H. Möhring and G. Steiner (1987) Computing the bump number of ordered sets is easy’, Report No. 87475, Institut fur Operations Research, University of Bonn, West Germany

    Google Scholar 

  58. P. Hanlon (1982) Counting interval graphs’, Trans. Amer. Math. Soc. 272, 383–426

    MathSciNet  MATH  Google Scholar 

  59. F. Harary and Z.R. Norman (1960) ‘Some properties of line digraphs’, Rend. Circ. Math. Palermo 9, 161–168

    MathSciNet  MATH  Google Scholar 

  60. D. Harel and R.E. Tarjan (1984) ‘East algorithms for finding nearest common ancestors’, SIAM J. Comput. 13, 338–355

    MathSciNet  MATH  Google Scholar 

  61. R.L. Hemminger and L.W. Beineke (1978) ‘Line graphs and line digraphs’, in: L.W. Beineke, R.J. Wilson, eds., Selected Topics in Graph Theory (Academic Press, London, 1978) 271–305

    Google Scholar 

  62. C. Heuchenne (1964) ‘Sur une certaine correspondance entre graphes’, Bull. Soc. Roy. Sci., Liège 33, 743–753

    MathSciNet  MATH  Google Scholar 

  63. T. Hiraguchi (1951) ‘On the dimension of partially ordered sets’, Sci. Rep. Kana-zawa Univ. 1, 77–94

    MathSciNet  MATH  Google Scholar 

  64. D.S. Johnson (1982–87) ‘The JVP-completeness column: an ongoing guide’, J. Algorithms 3 ff

    Google Scholar 

  65. H.A. Jung (1978) ‘On a class of posets and the corresponding comparability graphs’, J. Comb. Th. (B) 24, 125–133

    MATH  Google Scholar 

  66. R. Kaerkes (1970) ‘Zum Begriff des orientierten Graphen’, Methods of Oper. Res. 7, 122–125

    Google Scholar 

  67. R. Kaerkes (1977) ‘Netzplan Theory’ Methods of Oper. Res., 27, 1–65

    MathSciNet  Google Scholar 

  68. R. Kaerkes and R.H. Möhring (1978) Vorlesungen uber Ordnungen und Netzplan-therie, Schriften zur Informatik und Angewandten Mathematik 45, RWTH Aachen

    Google Scholar 

  69. A. Kaldewaij (1985) ‘On the decomposition of sequences’, Inform. Process. Letters 21, 69

    MathSciNet  MATH  Google Scholar 

  70. D. Kelly (1985) ‘Comparability graphs’, in [Ri3], 3–40

    Google Scholar 

  71. D. Kelly and W.T. Trotter, Jr. (1982) ‘Dimension theory for ordered sets’, in [Ri2], 171–211

    Google Scholar 

  72. N. Korte (1987) ‘Intervallgraphen und MPQ-Bäume: Algorithmen und Daten-strukturen zur Manipulation von Intervallgraphen und der Lösung von Serations-problemen, ’Report No. 87461-Or Thesis, Institut für Operations Research, University of Bonn, West Germany

    Google Scholar 

  73. N. Korte und R.H. Möhring (1985) ‘Transitive orientation of graphs with side constraints’, in H. Noltemeier (ed.) Procedings of WG’85, Trauner Verlag, 143–160

    Google Scholar 

  74. N. Korte und R.H. Möhring (1986) ‘A simple linear-time algorithm to recognize interval graphs’, Report No. 86421-OR, Institut für Operations Research, Universität Bonn, to appear in SIAM J. Comput.

    Google Scholar 

  75. M.S. Krishnamoorthy and N. Deo (1979) ‘Complexity of the minimum-dummy-activities problem in a PERT network’, Networks 9, 189–194

    MathSciNet  MATH  Google Scholar 

  76. E.L. Lawler (1976) Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York

    MATH  Google Scholar 

  77. E.L. Lawler (1976) ‘Graphical algorithms and their complexity’, Math. Centre Tracts 81, 3–32

    Google Scholar 

  78. E.L. Lawler (1978) ‘Sequencing jobs to minimize total weighted completion time subject to precedence constraints’, Ann. Discrete Math. 2, 75–90

    MathSciNet  MATH  Google Scholar 

  79. E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan (1982) ‘Recent developments in deterministic sequencing and scheduling: A survey’, in M.A.H. Dempster et al. (eds.) Deterministic and Stochastic Scheduling, Reidel, Dordrecht, 35–73

    Google Scholar 

  80. B. Leclerc and B. Monjardet (1973) ‘Orders “C.A.C”’, Fund. Math. 79, 11–22

    MathSciNet  MATH  Google Scholar 

  81. T. Lengauer and R. Müller (1986) ‘Linear algorithms for optimizing the layout of dynamic CMOS cells’, Report No. 32, Fachbereich Mathematik-Informatik, Universität Paderborn, West-Germany

    Google Scholar 

  82. N. Linial (1986) ‘Hard enumeration problems in geometry and combinatorics’, SIAM J. Alg. Disc. Meth. 7, 331–335

    MathSciNet  MATH  Google Scholar 

  83. N. Linial and M.E. Saks (1985) ‘Searching ordered structures’, J. Algorithms 6, 86–103

    MathSciNet  MATH  Google Scholar 

  84. G.S. Lueker and K.S. Booth (1979) ‘A linear time algorithm for deciding interval graph isomorphism’, J. ACM 26, 183–195

    MathSciNet  MATH  Google Scholar 

  85. E. Mayr (1981) ‘Well structered programs are not easier to schedule’, Report Stan-CS-81–880, Department of Computer Science, Stanford University

    Google Scholar 

  86. J.J. Moder and CR. Phillips (1964) Project management with CPM and PERT, Reinhold, New York

    Google Scholar 

  87. R.H. Möhring (1982) ‘Scheduling problems with a singular solution’, Ann. Discrete Math. 16, 225–239

    MATH  Google Scholar 

  88. R.H. Möhring (1983) ‘On the characterization of series-parallel networks, complement reducible graphs, and threshold graphs’, Methods of Oper. Res. 45, 287–291

    Google Scholar 

  89. R.H. Möhring (1984) ‘Almost all comparability graphs are UPO’, Discrete Math. 50, 63–70

    MathSciNet  MATH  Google Scholar 

  90. R.H. Möhring (1985) ‘Algorithmic aspects of comparability graphs and interval graphs’, in [Ri3], 41–101

    Google Scholar 

  91. R.H. Möhring und F.J. Radermacher (1984) ‘Substitution decomposition of discrete structures and connections with combinatorial optimization’, Annals Discrete Math. 19, 257–356

    Google Scholar 

  92. R.H. Möhring und F.J. Radermacher (1985) ‘Generalized results on the polyno-miality of certain weighted sum scheduling problems’, Methods of Oper. Res. 49, 405–417

    MATH  Google Scholar 

  93. C.L. Monma and J.B. Sidney (1979) ‘Sequencing with series-parallel precedence constraints’, Math. of Oper. Res. 4, 215–224

    MathSciNet  MATH  Google Scholar 

  94. C.L. Monma and J.B. Sidney (1987) ‘Optimal sequencing via modular decomposition: Characterization of sequencing functions’, Math. Oper. Res. 12, 22–31

    MathSciNet  MATH  Google Scholar 

  95. J.H. Muller and J. Spinrad (1984) ‘On-line modular decomposition’, Technical report GIT-ICS-84/11, Georgia Institute of Technology, to appear in J. ACM

    Google Scholar 

  96. O. Ore (1962) Theory of Graphs, Coll. Publ. 38, Amer. Math. Soc, Providence, R.I.

    MATH  Google Scholar 

  97. C.H. Papadimitriou and M. Yannakakis (1979) Scheduling interval-ordered tasks’, SIAM J. Comp. 8, 405–409

    MathSciNet  MATH  Google Scholar 

  98. A. Pnueli, A. Lempel and W. Even (1971) ‘Transitive orientation of graphs and identification of permutation graphs’ Canad. J. Math. 23, 160–175

    MathSciNet  MATH  Google Scholar 

  99. J.S. Provan and M.O. Ball (1983) ‘The complexity of counting cuts and of the probability that a graph is connected’, SIAM J. Comput. 12, 777–788

    MathSciNet  MATH  Google Scholar 

  100. W.R. Pulleyblank (1981) On minimizing setups in precedence constrained scheduling problems’, Report 81185-OR, Institut fur Operations Research, University of Bonn, West Germany

    Google Scholar 

  101. I. Rabinovitch (1978) ‘The dimension of semiorders’, J. Comb. Th.(A) 25, 50–61

    MathSciNet  MATH  Google Scholar 

  102. I. Rabinovitch (1978) ‘An upper bound on the dimension of interval orders’, J. Comb. Th.(A) 25, 68–71

    MathSciNet  MATH  Google Scholar 

  103. F.J. Radermacher (1977) ‘Floats in project networks’, Methods of Oper. Res. 27, 163–224

    MathSciNet  Google Scholar 

  104. F.J. Radermacher (1986) ‘Scheduling of project networks’, Annals of Oper. Res. 4, 227–252

    MathSciNet  Google Scholar 

  105. F.J. Radermacher (1986) ‘Schedule-induced posets’, Discrete Appl. Math. 14, 67–91

    MathSciNet  MATH  Google Scholar 

  106. F.J. Radermacher (1987) Characterization of the critical posets in two-machine unit time scheduling, preprint, University of Passau, West Germany

    Google Scholar 

  107. F. Rendl (1986) ‘Quadratic assignment problems on series-parallel digraphs’, Zeitschrift Oper. Res. 30(A) 161–173

    MathSciNet  MATH  Google Scholar 

  108. I. Rival (1982) ‘Optimal linear extensions by interchanging chains’, Proc. Amer. Math. Soc. 89, 387–394

    MathSciNet  Google Scholar 

  109. I. Rival (1982) (ed.) Ordered Sets, Reidel, Dordrecht

    MATH  Google Scholar 

  110. I. Rival (1985) (ed.) Graphs and Order, Reidel, Dordrecht

    MATH  Google Scholar 

  111. I. Rival and N. Zaguia (1986) ‘Constructing N-free, jump-critical ordered sets’, Congressus Num. 55, 199–204

    MathSciNet  Google Scholar 

  112. F.S. Roberts (1976) Discrete Mathematical Models, with Applications to Social, Biological and Environmental Problems, Prentice Hall, Englewood Cliffs, NJ

    MATH  Google Scholar 

  113. D.J. Rose, R.E. Tarjan, and G.S. Luecker (1976) ‘Algorithmic aspects of vertex elimination on graphs’, SIAM J. Comput. 5, 266–283

    MathSciNet  MATH  Google Scholar 

  114. M.E. Saks (1985) ‘The information theoretic bound for problems on ordered sets and graphs’, in [Ri3], 137–168

    Google Scholar 

  115. B. Sands (1981) ‘Counting antichains in finite partially ordered sets’, Discrete Math. 35, 213–228

    MathSciNet  MATH  Google Scholar 

  116. A.A. Schäfer and B.B. Simons (1987) ‘Computing the bump number of a partial order with techniques from two-processor scheduling’, preprint

    Google Scholar 

  117. D. Seinsche (1974) ‘On a property of the class of η-colorable graphs’, J. Comb. Th.(B) 16, 191–193

    MathSciNet  MATH  Google Scholar 

  118. S. Shinoda, Y. Kajitani, K. Onaga, W. Mayeda (1979) ‘Various characterizations of series-parallel graphs’, Proc. 1979 ISCHS, 100–103

    Google Scholar 

  119. J.B. Sidney (1975) ‘Decomposition algorithms for single machine sequencing with precedence relations and deferral costs’, Oper. Res. 23, 283–298

    MathSciNet  Google Scholar 

  120. J.B. Sidney and G. Steiner (1986) ‘Optimal sequencing by modular decomposition: polynomial algorithms’, Oper. Res. 34, 606–612

    MathSciNet  MATH  Google Scholar 

  121. D.J. Skrien (1982) ‘A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs’, J. Graph Theory 6, 309–316

    MathSciNet  MATH  Google Scholar 

  122. D.J. Skrien (1984) Chronological orderings of interval graphs’, Discrete Appl. Math. 8, 69–83

    MathSciNet  MATH  Google Scholar 

  123. D.J. Skrien and J. Gimble (1985) ‘Homogeneousely representable interval graphs’, Discrete Math. 55, 213–216

    MathSciNet  MATH  Google Scholar 

  124. J. Spinrad (1982) Two dimensional partial orders, Ph.D. Thesis, Princeton University

    Google Scholar 

  125. J. Spinrad (1984) ‘Bipartite permutation graphs’, preprint, School of ICS, Georgia Inst, of Technology, Atlanta

    Google Scholar 

  126. J. Spinrad (1984) ‘The minimum dummy task problem’, preprint School of ICS, Georgia Inst, of Technology, Atlanta

    Google Scholar 

  127. J. Spinrad (1985) ‘On comparability and permutation graphs’, SIAM J. Comput. 14, 658–670

    MathSciNet  MATH  Google Scholar 

  128. J. Spinrad (1987) ‘Potrees and substitution decomposition’, preprint, Dept. of Computer Science, Vanderbilt Univ., Nashville, Tennesse

    Google Scholar 

  129. J. Spinrad and J. Valdes (1983) ‘Recognition and isomorphism of two dimensional partial orders’, 10th Coll. on Automata, Language and Programming. Lecture Notes in Computer Science 154, Springer, Berlin, 676–686

    Google Scholar 

  130. G. Steiner (1984) ‘Single machine scheduling with precedence constraints of dimension 2’, Math. Oper. Res. 9, 248–259

    MathSciNet  MATH  Google Scholar 

  131. G. Steiner (1985) ‘A compact labeling scheme for series-parallel graphs’, Discrete Appl. Math. 11, 281–297

    MathSciNet  MATH  Google Scholar 

  132. G. Steiner (1985) ‘On finding the jump number of a partial order by substitution decomposition’, Order 2, 9–23

    MathSciNet  MATH  Google Scholar 

  133. G. Steiner (1986) ‘An algorithm to generate the ideals of a partial order’, Oper. Res. Letters 5, 317–320

    MathSciNet  MATH  Google Scholar 

  134. [ G. Steiner (1985) ‘Searching in 2-dimensional partial orders’, Report No 240, Faculty of Business, McMaster University, Hamilton, Ontario

    Google Scholar 

  135. G. Steiner (1987) ‘Minimizing bumps in ordered sets by substitution decomposition’, preprint, Faculty of Business, McMaster University, Hamilton, Ontario

    Google Scholar 

  136. G. Steiner (1987) ‘On computing the information theoretic bound for sorting: counting the linear extensions of posets’, preprint, Faculty of Business, McMaster University, Hamilton, Ontario

    Google Scholar 

  137. G. Steiner (1987) ‘On the information theoretic bound for sorting: balancing the linear extensions of posets’, preprint. Faculty of Business, McMaster University, Hamilton, Ontario

    Google Scholar 

  138. G. Steiner and L.K. Stewart (1987) ‘A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders’, Order 3, 359–367

    MathSciNet  MATH  Google Scholar 

  139. L.K. Stewart (1985) Permutation graph structure and algorithms, Thesis, Department of Computer Science, University of Toronto

    Google Scholar 

  140. L.K. Stewart (1986) ‘Permutation graph structure’, Congressus Num. 54, 87–100

    Google Scholar 

  141. D.P. Sumner (1973) ‘Graphs undecomposable with respect to the X-join’, Discrete Math, 6, 281–298

    MathSciNet  MATH  Google Scholar 

  142. D.P. Sumner (1974) ‘Dacey graphs’, J. Australian Math. Soc. 18, 492–502

    MathSciNet  MATH  Google Scholar 

  143. K.J. Supowit (1985) ‘Decomposing a set of points into chains, with applications to permutation and circle graphs’, Inform. Processing Letters 21, 249–252

    MathSciNet  MATH  Google Scholar 

  144. M.M. Syslo (1982) ‘A labeling algorithm to recognize a line digraph and output its root graph’, Inform. Processing Letters 15, 241–260

    MathSciNet  Google Scholar 

  145. M.M. Syslo (1984) ‘On the computational complexity of the minimum-dummy-activities problem in a PERT network’, Networks 14, 37–45

    MATH  Google Scholar 

  146. M.M. Syslo (1984) ‘Series-parallel graphs and depth-first search trees’, IEEE Trans, on Circuits and Systems CAS-31, 1029–1033

    MathSciNet  Google Scholar 

  147. M.M. Syslo (1985) ‘A graph theoretic approach to the jump number problem’, in [Ri3], 185–215

    Google Scholar 

  148. K. Takamizawa, T. Nishizeki, N. Saito (1982) ‘Linear-time computability of combinatorial problems on series-parallel graphs’, J. ACM 29, 623–641

    MathSciNet  MATH  Google Scholar 

  149. W.T. Trotter, Jr., J.I. Moore, Jr. and P. Sumner (1976) ‘The dimension of a comparability graph’, Proc. Amer. Math. Soc. 60, 35–38

    MathSciNet  Google Scholar 

  150. J. Valdes (1978) ‘Parsing flowcharts and series-parallel graphs’, Technical report STAN-CS-78–682, Computer Science Department, Stanford University, Stanford, Ca.

    Google Scholar 

  151. J. Valdes, R.E. Tarjan and E.L. Lawler (1982) ‘The recognition of series-parallel digraphs’, SIAM J. Comput. 11, 298–314

    MathSciNet  MATH  Google Scholar 

  152. M. Yannakakis (1982) ‘The complexity of the partial order dimension problem’, SIAM J. Discr. Meth. 3, 351–358

    MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Technical University of Berlin, Straße des 17. Juni 135, 1000, Berlin 12, Germany

    Rolf H. Möhring

Authors
  1. Rolf H. Möhring
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Departments of Computer Science and Mathematics, University of Ottawa, Ottawa, Canada

    Ivan Rival

Rights and permissions

Reprints and permissions

Copyright information

© 1989 Kluwer Academic Publishers

About this chapter

Cite this chapter

Möhring, R.H. (1989). Computationally Tractable Classes of Ordered Sets. In: Rival, I. (eds) Algorithms and Order. NATO ASI Series, vol 255. Springer, Dordrecht. https://doi.org/10.1007/978-94-009-2639-4_4

Download citation

  • DOI: https://doi.org/10.1007/978-94-009-2639-4_4

  • Publisher Name: Springer, Dordrecht

  • Print ISBN: 978-94-010-7691-3

  • Online ISBN: 978-94-009-2639-4

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation