Some aspects of perfect elimination orderings in chordal graphs. (English) Zbl 0537.05069

The present paper intends to study properties of perfect elimination orderings in chordal graphs. Their connections to convex subsets and quasiconcave functions in a graph are discussed. Schemes for generating all perfect elimination orderings are investigated and related to the existing schemes.
Reviewer: B.Dass


05C99 Graph theory
94B10 Convolutional codes
Full Text: DOI


[1] Buneman, P., A characterisation of rigid circuit graphs, Discrete math., 9, 205-212, (1974) · Zbl 0288.05128
[2] Chandrasekaran, R.; Tamir, A., Polynomially bounded algorithms for locating p-centers on a tree, Math. programming, 22, 304-315, (1982) · Zbl 0486.90036
[3] Dirac, G.A., (), 71-76
[4] Fulkerson, D.R.; Gross, O.A., Incidence matrices and interval graphs, Pacific J. math., 15, 835-855, (1965) · Zbl 0132.21001
[5] Gavril, F., Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J. comput., 1, 180-187, (1972) · Zbl 0227.05116
[6] Golumbic, M., Algorithmic graph theory and perfect graphs, (1980), Academic Press New york · Zbl 0541.05054
[7] M. Golumbic, Algorithmic aspects of perfect graphs, Ann. Discrete Math., to appear. · Zbl 0557.68044
[8] A. Hoffman and M. Sakarovitch, personal communication.
[9] Jamison, R., Copoints in antimatroids, Congressus numerantium, 29, 535-544, (1980) · Zbl 0463.05005
[10] Jamison, R., A perspective on abstract convexity: classifying alignments by varieties, (), 113-150
[11] Lekkerkerker, C.; Boland, J., Representation of a finite graph by a set of intervals on the real line, Fund. math., 51, 45-64, (1962) · Zbl 0105.17501
[12] Mangasarian, O., Nonlinear programming, (1969), McGraw-Hill New York · Zbl 0127.36803
[13] Papadimitriou, C.; Yannakakis, M., Scheduling interval-ordered tasks, SIAM J. comput., 8, 405-409, (1979) · Zbl 0421.68040
[14] Rose, D., Triangulated graphs and the elimination process, J. math. anal. appl., 32, 597-609, (1970) · Zbl 0216.02602
[15] Rose, D., A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, (), 183-217
[16] Rose, D.; Tarjan, R.; Lueker, G., Algorithmic aspects of vertex elimination on graphs, SIAM J. comput., 5, 266-283, (1976) · Zbl 0353.65019
[17] Tarjan, R., Maximum cardinality search and chordal graphs, (1976), Stanford University, Unpublished lecture notes
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.