INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs
Kratochvíl, Jan ; Nešetřil, Jaroslav
Commentationes Mathematicae Universitatis Carolinae, Tome 031 (1990), p. 85-93 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)
Publié le : 1990-01-01
Classification:  05C85,  05C99,  68Q25,  68R10 
@article{106821,
     author = {Jan Kratochv\'\i l and Jaroslav Ne\v set\v ril},
     title = {INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     volume = {031},
     year = {1990},
     pages = {85-93},
     zbl = {0727.05056},
     mrnumber = {1056173},
     language = {en},
     url = {http://dml.mathdoc.fr/item/106821}
}

Kratochvíl, Jan; Nešetřil, Jaroslav. INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs. Commentationes Mathematicae Universitatis Carolinae, Tome 031 (1990) pp. 85-93. http://gdmltest.u-ga.fr/item/106821/

Ehrlich G.; Even S.; Tarjan R. E. Intersection graphs of curves in the plane, J. Combin. Th. Ser. B 21 (1976), 8-20. (1976) | MR 0505857 | Zbl 0348.05113

De Fraysseix H.; Pach J.; Pollack R. Small sets supporting Fáry embeddings of planar graphs, STOC 1988. (1988)

Gavril F. Algorithms for a maximum clique and maximum independent set of a circle graph, Networks 4 (1973), 261-273. (1973) | MR 0340106

Garey M. R.; Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979. (1979) | MR 0519066 | Zbl 0411.68039

Kratochvíl J. String graphs I. The number of critical nonstring graphs is infinite, (to appear in J. Combin. Th. Ser. B). | MR 1109419

Kratochvíl J. String graphs II. Recognizing string graphs in NP-hard, (to appear in J. Combin. Th. Ser. B). | MR 0737032

Kratochvíl J.; Goljan M.; Kučera P. String graphs, Rozpravy československé akademie věd, ŘMPV 96, No. 3, Academia, Prague, 1986. (1986) | MR 0865778

Kratochvíl J.; Matoušek J. Intersections graphs of segments, submitted.

Kratochvíl J.; Matoušek J. NP-hardness results for intersection graphs, Comment. Math. Univ. Carolinae 30 (1989), 761-773. (1989) | MR 1045907

Middendorf M.; Pfeiffer F. Max clique problem in classes of string graphs, preprint Univ. Bonn (1988). (1988) | MR 1189857

Sinden F. W. Topology of thin film RC circuits, Bell System Tech. J. (1966), 1639-1662. (1966) | Zbl 0144.45601

Valiant L. G. Universality considerations in VLSI circuits, IEEE Trans. Comput. 30 (1981), 135-140. (1981) | MR 0605722 | Zbl 0455.94046