NP-hardness results for intersection graphs
Kratochvíl, Jan ; Matoušek, Jiří
Commentationes Mathematicae Universitatis Carolinae, Tome 030 (1989), p. 761-773 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)
Publié le : 1989-01-01
Classification:  05C75,  05C85,  05C99,  68Q25,  68R10 
@article{106799,
     author = {Jan Kratochv\'\i l and Ji\v r\'\i\ Matou\v sek},
     title = {NP-hardness results for intersection graphs},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     volume = {030},
     year = {1989},
     pages = {761-773},
     zbl = {0697.05052},
     mrnumber = {1045907},
     language = {en},
     url = {http://dml.mathdoc.fr/item/106799}
}

Kratochvíl, Jan; Matoušek, Jiří. NP-hardness results for intersection graphs. Commentationes Mathematicae Universitatis Carolinae, Tome 030 (1989) pp. 761-773. http://gdmltest.u-ga.fr/item/106799/

K. S. Booth G. S. Lucker Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. Syst. Sci 13 (1976), 255-265. (1976) | MR 0433962

A. Bouchet Reducing prime graphs and recognizing circle graphs, Combinatorica 7 (1987), 243-254. (1987) | MR 0918395 | Zbl 0666.05037

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

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

J. C. Fournier Une caractenzation dęs graphes de cordes, C.R. Acad. Sci. Paris 286A (1978), 811-813. (1978) | MR 0498269

D. F. Fulkerson O. A. Gross Incidence matrices with the consecutive 1 's property, Bull. Amer. Math. Soc. 70 (1965), 681-684. (1965)

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

P. C. Gilmore A. J. Hoffman A characterization of interval graphs and of comparability graphs, Canad. Math. J. 16 (1964), 539-548. (1964) | MR 0175811

J. Kratochvíl M. Goljan P. Kučera String graphs, Academia, Prague 1986. (1986) | MR 0865778

J. Kratochvíl J. Matoušek Intersection graphs of segments, KAM Series, Charles University Prague, 1989. (1989)

J. Kratochvíl M. Křivánek Satisfiability of almost satisfied formulas, (in Czech), in Proceedings Czechoslovak Conference on Graph Theory, Hrubá Skála 1989., Acta Univ. Hamm. Ham. 1 (1989), 11. (1989)

J. Kratochvíl String graphs II Recognizing siring graphs is NP-hard, to appear in J. Comb. Theory Ser. B. | MR 0737032

J. Kratochvíl A special planar satisfiability problem and some consequences of its NP-completeness, submitted.

C. B. Lekkerker J. C. Boland Representation of finite graphs by a set of intervals on the real line, Fund. Math 51 (1962), 45-64. (1962) | MR 0139159

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

A. C. Tucker An algorithm for circular-arc graphs, SIAM J. Computing 31. 2 (1980), 211-216. (1980) | MR 0557822