Abstract
Using the notion ofG-decomposition introduced in Golumbic [8, 9], we present an implementation of an algorithm which assigns a transitive orientation to a comparability graph inO(δ·|E|) time andO(|E|) space where δ is the maximum degree of a vertex and |E| is the number of edges. A quotient operation reducing the graph in question and preservingG-decomposition and transitive orientability is shown, and efficient solutions to a number ofNP-complete problems which reduce to polynomial time for comparability graphs are discussed.
Zusammenfassung
Wir verwenden den in Golumbic [8, 9] eingeführten Begriff derG-Zerlegung, um eine Implementierung eines Algorithmus anzugeben, der einem transitiv orientierbaren Graphen eine transitive Orientierung in ZeitO(δ·|E|) und PlatzO(|E|) zuordnet, wobei δ der maximale Grad eines Knoten und |E| die Anzahl der Kanten ist. Wir zeigen eine Quotientenoperation, die den betrachteten Graphen reduziert undG-Zerlegung und transitive Orientierbarkeit bewahrt, und es werden effiziente Lösungen einigerNP-vollständiger Probleme diskutiert, die, für transitiv orientierbare Graphen, in Polynomzeit lösbar sind.
Similar content being viewed by others
References
Berge, C.: Graphs and Hypergraphs, Chapter 16. Amsterdam: North-Holland 1973.
Even, S., Pnueli, A., Lempel, A.: Permutation graphs and transitive graphs. J. ACM19, 400–410 (1972).
Gallai, T.: Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hung.18, 25–66 (1967).
Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques and maximum independent set of a chordal graph. SIAM J. Comp.1, 180–187 (1972).
Ghouila-Houri, A.: Caractérisation des graphes nonorientés dont on peut orienter les arêtes de manière à obtenir le graphe d'une relation d'ordre. C. R. Acad. Sci. Paris254, 1370–1371 (1962).
Gilmore, P. C., Hoffman, A. J.: A characterization of comparability graphs and of interval graphs. Can. J. Math.16, 539–548 (1964).
Golumbic, M. C.: An infinite class of superperfect noncomparability graphs. IBM Research RC 5064 (October 1974).
Golumbic, M. C.: Comparability graphs and a new matroid (extended abstract). Proc. Alg. Aspects of Comb., Univ. of Toronto, January 1975.
Golumbic, M. C.: Comparability graphs and a new matroid. J. Comb. Th., SeriesB 22, 68–90 (1977).
Pnueli, A., Lempel, A., Even, S.: Transitive orientation of graphs and identification of permutation graphs. Can. J. Math.23, 160–175 (1971).
Shevrin, L. N., Filippov, N. D.: Partially ordered sets and their comparability graphs. Siberian Math. J.11, 497–509 (1970).
Author information
Authors and Affiliations
Additional information
This work was supported in part by NSF grant DCR-75-09218.
Rights and permissions
About this article
Cite this article
Golumbic, M.C. The complexity of comparability graph recognition and coloring. Computing 18, 199–208 (1977). https://doi.org/10.1007/BF02253207
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02253207