zbMATH — the first resource for mathematics

A recognition algorithm for the intersection graphs of paths in trees. (English) Zbl 0398.05060

05C99 Graph theory
05C38 Paths and cycles
05C05 Trees
05-04 Software, source code, etc. for problems pertaining to combinatorics
Full Text: DOI
[1] Booth, K.S.; Lueker, G.S., Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. comput. system sci., 13, 335-379, (1976) · Zbl 0367.68034
[2] Fulkerson, D.R.; Gross, O.A., Incidence matrices and interval graphs, Pacific J. math., 15, 835-855, (1965) · Zbl 0132.21001
[3] 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
[4] Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs, J. combinatorial theory ser. B, 16, 47-56, (1974) · Zbl 0266.05101
[5] Gavril, F., A recognition algorithm for the intersection graphs of directed paths in directed trees, Discrete math., 13, 237-249, (1975) · Zbl 0312.05108
[6] Gilmore, P.C.; Hoffman, A.J., A characterization of comparability graphs and of interval graphs, Can. J. math., 16, 539-548, (1964) · Zbl 0121.26003
[7] Karp, R.M., Reducibility among combinatorial problems, () · Zbl 0366.68041
[8] Klee, V., What are the intersection graphs of arcs in a circle?, Am. math. monthly, 76, 810-813, (1969)
[9] Pnueli, A.; Lempel, A.; Even, S., Transitive orientation of graphs and identification of permutation graphs, Can. J. math., 23, 160-175, (1971) · Zbl 0204.24604
[10] Renz, P.L., Intersection representations of graphs by arcs, Pacific J. math., 34, 501-510, (1970) · Zbl 0191.55103
[11] F.S. Roberts, Discrete Mathematical Models with Applications to Social, Biological and Environmental Problems (Prentice-Hall, Englewood Cliffs, NJ, to appear). · Zbl 0363.90002
[12] Rose, D.J.; Tarjan, R.E., Algorithmic aspects of vertex elimination, Proc. seventh ann. ACM symp. on the theory of computing, (1975) · Zbl 0382.05049
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.