Geodesic
NP-hardness results for intersection graphs
Commentationes Mathematicae Universitatis Carolinae, Tome 30 (1989) no. 4, pp. 761-773 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Classification : 05C75, 05C85, 05C99, 68Q25, 68R10 
@article{CMUC_1989_30_4_a18,
     author = {Kratochv{\'\i}l, Jan and Matou\v{s}ek, Ji\v{r}{\'\i}},
     title = {NP-hardness results for intersection graphs},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     pages = {761--773},
     year = {1989},
     volume = {30},
     number = {4},
     mrnumber = {1045907},
     zbl = {0697.05052},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMUC_1989_30_4_a18/}
}
TY  - JOUR
AU  - Kratochvíl, Jan
AU  - Matoušek, Jiří
TI  - NP-hardness results for intersection graphs
JO  - Commentationes Mathematicae Universitatis Carolinae
PY  - 1989
SP  - 761
EP  - 773
VL  - 30
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/CMUC_1989_30_4_a18/
LA  - en
ID  - CMUC_1989_30_4_a18
ER  - 
%0 Journal Article
%A Kratochvíl, Jan
%A Matoušek, Jiří
%T NP-hardness results for intersection graphs
%J Commentationes Mathematicae Universitatis Carolinae
%D 1989
%P 761-773
%V 30
%N 4
%U http://geodesic.mathdoc.fr/item/CMUC_1989_30_4_a18/
%G en
%F CMUC_1989_30_4_a18
Kratochvíl, Jan; Matoušek, Jiří. NP-hardness results for intersection graphs. Commentationes Mathematicae Universitatis Carolinae, Tome 30 (1989) no. 4, pp. 761-773. http://geodesic.mathdoc.fr/item/CMUC_1989_30_4_a18/

[BL] 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. | MR

[Bou] A. Bouchet: Reducing prime graphs and recognizing circle graphs. Combinatorica 7 (1987), 243-254. | MR | Zbl

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

[FPP] H. Fraysseix J. Pach R. Pollack: Small sets representing Fáry embeddings of planar graphs. Proceedings STOC 1988.

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

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

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

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

[KGK] J. Kratochvíl M. Goljan P. Kučera: String graphs. Academia, Prague 1986. | MR

[KM] J. Kratochvíl J. Matoušek: Intersection graphs of segments. KAM Series, Charles University Prague, 1989.

[KK] 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.

[Kra1] J. Kratochvíl: String graphs II Recognizing siring graphs is NP-hard. to appear in J. Comb. Theory Ser. B. | MR

[Kra2] J. Kratochvíl: A special planar satisfiability problem and some consequences of its NP-completeness. submitted.

[LB] 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. | MR

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

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