INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs
Jan Kratochvíl; Jaroslav Nešetřil
Commentationes Mathematicae Universitatis Carolinae (1990)
- Volume: 031, Issue: 1, page 85-93
- ISSN: 0010-2628
Access Full Article
top
How to cite
topKratochvíl, Jan, and Nešetřil, Jaroslav. "INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs." Commentationes Mathematicae Universitatis Carolinae 031.1 (1990): 85-93. <http://eudml.org/doc/17810>.
@article{Kratochvíl1990,
author = {Kratochvíl, Jan, Nešetřil, Jaroslav},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {string graphs; graph algorithms; intersection graphs; independent set; clique},
language = {eng},
number = {1},
pages = {85-93},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs},
url = {http://eudml.org/doc/17810},
volume = {031},
year = {1990},
}
TY - JOUR
AU - Kratochvíl, Jan
AU - Nešetřil, Jaroslav
TI - INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 1990
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 031
IS - 1
SP - 85
EP - 93
LA - eng
KW - string graphs; graph algorithms; intersection graphs; independent set; clique
UR - http://eudml.org/doc/17810
ER -
References
top- Ehrlich G., Even S., Tarjan R. E., Intersection graphs of curves in the plane, J. Combin. Th. Ser. B 21 (1976), 8-20. (1976) Zbl0348.05113MR0505857
- 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) MR0340106
- Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979. (1979) Zbl0411.68039MR0519066
- Kratochvíl J., String graphs I. The number of critical nonstring graphs is infinite, (to appear in J. Combin. Th. Ser. B). MR1109419
- Kratochvíl J., String graphs II. Recognizing string graphs in NP-hard, (to appear in J. Combin. Th. Ser. B). MR0737032
- Kratochvíl J., Goljan M., Kučera P., String graphs, Rozpravy československé akademie věd, ŘMPV 96, No. 3, Academia, Prague, 1986. (1986) MR0865778
- 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) MR1045907
- Middendorf M., Pfeiffer F., Max clique problem in classes of string graphs, preprint Univ. Bonn (1988). (1988) MR1189857
- Sinden F. W., Topology of thin film RC circuits, Bell System Tech. J. (1966), 1639-1662. (1966) Zbl0144.45601
- Valiant L. G., Universality considerations in VLSI circuits, IEEE Trans. Comput. 30 (1981), 135-140. (1981) Zbl0455.94046MR0605722
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.