Abstract
Comparability graphs are undirected graphs that represent the comparability relation of partial orders. They constitute an important interface between graphs and partial orders both for theoretical investigations on their structural properties, and the development of efficient algorithmic methods for otherwise NP-hard combinatorial (optimization) problems on partial orders and their comparability graphs.
The first part of the paper gives a survey of this second aspect of comparability graphs. Topics dealt with are algorithmic methods and the necessary theoretical background for comparability graph recognition, for constructing all partial orders with the same comparability graphs, for decomposing comparability graphs and partial orders, for determining comparability invariants such as order dimension or jump number by decomposition, and for solving combinatorial optimization problems on comparability graphs.
The second part deals with the related class of interval graphs, which are exactly the incomparability graphs of interval orders. Again, we represent algorithmic methods for interval graph recognition and for solving combinatorial optimization problems on these graphs.
We then demonstrate in the third part how comparability graphs and interval graphs can be used for solving specific applied problems such as the seriation problem in archeology or certain scheduling problems over partially ordered sets.
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
A.V. Aho, J.E. Hopcroft and J.D. Ullman (1975) The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Ma.
M. Aigner (1979) Combinatorial Theory, Springer, Berlin
M. Aigner and G. Prins (1971) Uniquely partially orderable graphs, J. London Math. Soc. 2, 260–266
J.C. Arditti (1976) Partially ordered sets and their comparability graphs, their dimension and their adjacency, Proc.Colloq. Int. CNRS., Problemes Combinatoires et Theorie des Graphes, Orsay, France.
J.C. Arditti and H.A. Jung (1980) The dimension of finite and infinite comparability graphs, J.London Math. Soc. 21, 31–38
M. Ashbacher (1976) A homomorphism theorem for finite graphs, Proc. Amer. Math. Soc.54, 468–470
R.L. Ashenhurst (1959) The decomposition of switching functions, in: Proceedings of the International Symposium on the Theory of Switching (Part I), Harvard University Press, Cambridge.
K.A. Baker, P.C. Fishburn and F.S. Roberts (1971) Partial orders of dimension 2, Networks 2, 11–28
K.R. Baker (1974) Introduction to Sequencing and Scheduling, Wiley, New York
E. Balas (1971) Project scheduling with resource constraints, in: E.M-L. Beale (ed.) Applications of Mathematical Programming, The English University Press, London, 187–200
R.E. Barlow and F. Proschan (1975) Statistical Theory of Reliability and Life Testing (Probability Models) Holt, Rinehart and Winston, New York
J.P. Barthélemy, C. Flament and B. Monjardet (1982) Ordered sets and social sciences, in [Ri1], 721–758
M. Bartusch (1981) An algorithm for generating all maximal independent subsets of a poset, Computing 26, 343–354
M. Bartusch (1983) Optimierung von Netzplänen mit Anordnungsbeziehungen bei knappen Betriebsmitteln, Thesis Techn. Univ. of Aachen
C. Berge(1973) Graphs and Hypergraphs, North Holland, Amsterdam
Z.W. Birnbaum and J.D. Esary (1965) Modules of coherent binay systems, SIAM J. Applied Math. 13, 444–462
A. Blass (1978) Graphs with unique maximal clumpings, J.Graph Th. 2, 19–24
K.P. Bogart (1982) Some social science applications of ordered sets, in [Ri1], 759–787
B. Bollobas (1978) Extremal Graph Theory, Academic Press,London
S. Booth and S. Lueker (1976) Testing for the consectutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J.Comput. Syst. Sci. 13, 335–379
H. Buer and R.H. Möhring (1983) A fast algorithm for the decomposition of graphs and posets, Math. Oper. Res. 8, 170–184
M. Chein and M. Habib (1980) The jump number of dags and posets: an introduction, Ann. of Discrete Math. 9, 189–194
J.E. Cohen, J. Komlós and T. Mueller (1979) The probability of an interval graph and why it matters, Proc. Sympos. Pure Math. 34, 97–115, Amer. Math. Soc., Providence, R.I.
R.W. Conway, W.L. Maxwell and L.W. Miller (1967) Theory of Scheduling, Addison-Wesley, Reading, MA
D. Coppersmith and S. Winograd (1982) On the asymptotic complexity of matrix multiplication, SIAM J. Computing 11, 472–492
D.G. Corneil, H. Lerchs and L. Stewart Burlingham (1981) Complement reducible graphs, Discr. Appl. Math. 3, 163–174
D.D. Cowan, L.O. James and R.G. Stanton (1972) Graph decomposition for undirected graphs, in: F. Hoffmann, R.B. Levow (eds.), 3rd South-Eastern Conf. Combinatorics, Graph Theory and Computing, Utilitas Math., Winnipeg, 281–290
W.H. Cunningham (1982) Decomposition of directed graphs, SIAM J. Algebraic and Discrete Methods 3, 214–228
W.H. Cunningham and J. Edmonds (1980) A combinatorial decomposition theory, Can. J. Math. 32, 734–765
H.A. Curtis (1962) A New Approach to the Design of Switching Circuits, van Nostrand, Princeton
R.P. Dilworth (1950) A decomposition theorem for partially ordered sets, Ann. Math. Ser. 251, 161–166
B. Dushnik and E. Miller (1941) Partially ordered sets, Amer. J. Math. 63, 600–610
S.E. Elmaghraby (1977) Activity Networks, Wiley, New York
S. Even (1979) Graph Algorithms, Pitman, London
U. Faigle, G. Gierz and R. Schrader (1983) Algorithmic approaches to setup minimization, Report No. 83297-OR, Institut für Ökonometrie und Operations Research, University of Bonn
U. Faigle and R. Schrader (1983) Comparability graphs and order invariants, Report No. 83308-0R, Institut für Ökonometrie und Operations Research, University of Bonn
P.C. Fishburn (1970) Intransitive indifference in preference theory: A survey. Oper.Res. 18, 207–228
L.R. Ford and D.R. Fulkerson (1962) Flows in Networks, Princeton Univ. Press, Princeton, New Jersey
A. Frank (1976) Some polynomial algorithms for certain graphs and hypergraphs, Proc. 5th British Comb. Conf., Congr. Num. No. XV, Utilitas Math., Winnipeg, 211–226
D.R. Fulkerson (1971) Blocking and anti-blocking pairs of polyhedra, Math. Progr.1, 168–194
D.R. Fulkerson (1972) Antiblocking polyhedra, J.Comb.Th. B 12, 50–71
D.R. Fulkerson and O.A. Gross (1965) Incidence matrices and interval graphs, Pacific J. Math. 15, 835–855
T. Gallai (1967) Transitiv orientierbare Graphen, Acta Math. Acad. Scient. Hung. Tom. 18, 25–66
F. Gavril (1972) Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J. Computing 2, 180–187
A. Ghouilà-Houri (1962) Characterisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graph d’une relation d’ordre C.R. Acad. Sci. Paris, 254, 1370–1371
P.C. Gilmore and A.J. Hoffman (1964) A characterization of comparability graphs and of interval graphs, Canad. J. Math. 16, 539–548
M.C. Golumbic (1977) Comparability graphs and a new matroid, J. Combin. Theory B 22, 68–90
M.C. Golumbic (1977) The complexity of comparability graph recognition and coloring. Computing 18, 199–208
M.C. Golumbic (1980) Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York
S. Gorenstein (1972) An algorithm for project (job) sequencing with resource constraints, Oper. Res. 20, 835–850
W.M. Gorman (1968) The structure of utility functions, Rev. Econ. Stud. 35, 367–390
P. Grillet (1969) Maximal chains and antichains, Fund.Math. 65, 157–167
M. Grötschel, L. Lovasz and A. Schrijver (1981) The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1, 169–197
U.I. Gupta, D.T. Lee and J.Y.-T. Leung (1982) Efficient algorithms for interval graphs and circular arc graphs, Networks 12, 459–467
R. Gysin (1977) Dimension transitiv orientierbarer Graphen, Acta Math. Aca. Sci. Hung 29, 313–319
M. Habib (1982) Comparability invariants, preprint
M. Habib and M.C. Mauser (1979) On the x-join decomposition for undirected graphs, J. Appl. Discr. Math. 3, 198–207
P. Hanlon (1982) Counting interval graphs, Trans, Amer. Math. Soc. 272, 383–426
R.L. Hemminger (1968) The group of an X-join of graphs, J. Comb. Th. 5, 408–418
T. Hiraguchi (1951) On the dimension of partially ordered sets, Sci. Rep. Kanazawa Univ. 1, 77–94
H. Igelmund and F.J. Radermacher (1983) Preselective strategies for the optimization of stochastic project networks under resource constraints, Networks 13, 1–28
R. Kaerkes (1977) Netzplan Theory, Methods of Oper. Res., 27, 1–65
R. Kaerkes and B. Leipholz (1977) Generalized network functions in flow networks, Methods of Oper. Res. 27, 225–273
R. Kaerkes and R.H. Möhring (1978) Vorlesungen über Ordnungen und Netzplantheorie, Schriften zur Informatik und Angewandten Mathematik 45, RWTH Aachen
R. Kaerkes, R.H. Möhring, W. Oberschelp, F.J. Radermacher, and M.M. Richter (1984) Netzplanoptimierung: Deterministische und stochastische Scheduling-Probleme über geordneten Strukturen, Springer Lecture Notes in Economics and Mathematical Systems, to appear
D. Kelly (1985) Comparability graphs, this volume
D. Kelly and W.T. Trotter, Jr. (1982) Dimension theory for ordered sets, in [Ri1], 171–211
D.J. Kleitmann and B.L. Rothschild (1975) Asymptotic enumeration of partial orders on a finite set, Trans. Amer. Math. Soc. 205, 205–220
N. Korte and R.H. Möhring (1984) A resource levelling algorithm based on interval graph recognition and generation, preprint, Techn. Univ. of Aachen
E.L. Lawler (1976) Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York
E.L. Lawler (1978) Sequencing jobs to minimize total weighted completion time subject to precedence constraints, Ann. Discrete Math.2, 75–90
E.L Lawler and J.K. Lenstra (1982) Machine scheduling with precedence constraints, in [Ri1], 655–675
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
B. Leclerc and B. Monjardet (1973) Orders “C.A.C.”, Fund. Math. 79, 11–22
L. Lovasz (1972) A characterization of perfect graphs, J.Comb. Th.B 13, 95–98
N. Megiddo (1975) Tensor decomposition of cooperative games, SIAM J. Appl. Math. 29, 388–405
L. Mirsky (1971) A dual of Dilworth’s decomposition theorem, Amer. Math.Monthly 78, 876–877
J.J. Moder and C.R. Phillips (1964) Project management with CPU and PERT, Reinhold, New York
R.H. Möhring (1982) Scheduling problems with a singular solution, Ann. discrete Math. 16, 225–239
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
R.H. Möhring (1984) Almost all comparability graphs are UPO, preprint, to appear in discrete Math.
R.H. Möhring (1984) Minimizing costs of resource requirements in project networks subject to a fixed completion time, Oper. Res. 32, 89–120
R.H. Möhring and F.J. Radermacher (1983) Dimension, reversibility and chain-equivalence of posets, and connections with homomorphism, in: M. Beckmann, W. Eichhorn and W. Krelle (eds.) Mathematische Systeme in der Ökonomie, Konigstein (Ts), 415–432
R.H. Möhring and F.J. Radermacher (1982) Substitution decomposition of discrete structures and connections with combinatorial optimization, preprint, to appear in Ann. Discrete Math.
R.H. Möhring and F.J. Radermacher (1984) Scheduling problems with resource-duration interaction, Methods of Oper. Res. 48, 423–452
C.L. Monma and J.B. Sidney (1979) Sequencing with series- parallel precedence constraints, Math, of Oper. Res. 4, 215–224
J.H. Muller and J. Spinrad (1984) On-line modular decomposition, Technical report GIT-ICS-84/11, Georgia Institute of Technology
C.H. Papadimitriou and M. Yannakakis (1979) Scheduling in- terval-ordered tasks, SIAM J. Comp. 8, 405–409
J. Patterson, R. Slowinski, B. Talbot and J. Weglarz (1982) An Algorithm for a general class of precedence and resource constrained scheduling problems, preprint
A. Pnueli, A. Lempel and W. Even (1971) Transitive orientation of graphs and identification of permutation graphs. Canad. J. Math. 23, 160–175
F.J. Radermacher (1978) Kapazitätsoptimierung in Netzplänen, Math. Syst. in Econ. 40, Anton Hain, Meisenheim
F.J. Radermacher (1981) Ein Faktorisierungssatz für die Möbiusfunktion, paper presented at the “23. Kurztagung über Allgemeine Algebra”, Kaiserslautern
F.J. Radermacher (1981) Cost-dependent essential systems of ES-strategies for stochastic scheduling problems, Methods of Oper. Res. 42, 17–31
F.J. Radermacher (1982) Optimization of resource constrained project networks, preprint, Techn. Univ. of Aachen
F.J. Radermacher and H.G. Spelde (1974) Reduktion von Fluß-netzplänen, Proceedings in Oper. Res. 3, 177–186
R.C. Read and N.C. Wormland (1980) Catalogues of graphs and digraphs, Discrete Math. 31, 224–225
A.H.G. Rinnooy Kan (1976) Machine Scheduling Problems: Classification, Complexity and Computation, Nijhoff, The Hague
J. Riordan (1958) An Introduction to Combinatorial Analysis, J. Wiley & Sons, New York
I. Rival (ed.) (1982) Ordered Sets, Reidel. Dordrecht
I. Rival (1982) Optimal linear extensions by interchanging chains, Proc. Amer. Math. Soc. 89, 387–394
F.S. Roberts (1976) Discrete Mathematical Models, with Applications to Social, Biological and Environmental Problems, Prentice Hall, Englewood Cliffs, NJ
D.J. Rose, R.E. Tarjan and G.S. Lueker (1976) Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput. 5, 266–283
G. Sabidussi (1961) Graph derivatives, Math. Zeitschrift 76, 385–401
L.S. Shapley (1967) On Committees, in New Methods of Thought and Procedure, F. Zwicky, A. G. Wilson (eds.) Springer Verlag, Berlin, New York, 246–270
L.N. Shevrin and N.D. Filippov (1970) Partially ordered sets and their comparability graphs, Siber. Math. J. 11, 497–509
A.W. Shogan (1978) A decomposition algorithm for network reliability analysis, Networks 8, 231–252
J. Spinrad (1982) Two dimensional partial orders, Ph.D. Thesis, Princeton University
J. Spinrad (1983) On comparability and permutation graphs, Technical Report GIT-ICS-83/10, Georgia Institute of Technology
R.P. Stanley (1973) A Brylawski decomposition for finite ordered sets, Discrete Math. 4, 77–82
K. Strassner (1981) Zur Strukturtheorie endlicher nichtdeter-ministischer Automaten I: Zum Verband der 1-Kongruenzen von endlichen Relationalsystemen, J. Information Processing and Cybernetics(EIK) 17, 113–120
M.M. Syslo (1984) Minimizing the jump number for partially ordered sets: a graph-theoretic approach, ORDER 1, 7–20.
M.M. Syslo (1985) A graph theoretic approach to the jump number problem, this volume
M.M. Syslo, N. Deo and J.S. Kowalik (1983) Discrete Optimization Algorithms with Pascal Programs, Prentice Hall, Englewood Cliffs, N.J.
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
J. Valdes, R.E. Tarjan and E.L. Lawler (1979) The recognition of series-parallel digraphs. Proc. 11th Annual ACM Syrrrp. on Theory of Comp. ACM, 1–12
R. Wille (1983) Lexicographic decomposition of ordered sets (graphs), Preprint No 705, Fachbereich Mathematik, Techn. Univ. of Darmstadt
M. Yannakakis (1982) The complexity of the partial order dimension problem, SIAM J. Alg. Disc. Math. 3, 351–358
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1985 D. Reidel Publishing Company
About this chapter
Cite this chapter
Möhring, R.H. (1985). Algorithmic Aspects of Comparability Graphs and Interval Graphs. In: Rival, I. (eds) Graphs and Order. NATO ASI Series, vol 147. Springer, Dordrecht. https://doi.org/10.1007/978-94-009-5315-4_2
Download citation
DOI: https://doi.org/10.1007/978-94-009-5315-4_2
Publisher Name: Springer, Dordrecht
Print ISBN: 978-94-010-8848-0
Online ISBN: 978-94-009-5315-4
eBook Packages: Springer Book Archive