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

How to cite

top

Kratochví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
  1. 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
  2. de Fraysseix H., Pach J., Pollack R., Small sets supporting Fáry embeddings of planar graphs, STOC 1988. (1988) 
  3. Gavril F., Algorithms for a maximum clique and maximum independent set of a circle graph, Networks 4 (1973), 261-273. (1973) Zbl0259.05125MR0340106
  4. Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979. (1979) Zbl0411.68039MR0519066
  5. Kratochvíl J., String graphs I. The number of critical nonstring graphs is infinite, (to appear in J. Combin. Th. Ser. B). Zbl0675.05058MR1109419
  6. Kratochvíl J., String graphs II. Recognizing string graphs in NP-hard, (to appear in J. Combin. Th. Ser. B). Zbl0661.05054MR0737032
  7. Kratochvíl J., Goljan M., Kučera P., String graphs, Rozpravy československé akademie věd, ŘMPV 96, No. 3, Academia, Prague, 1986. (1986) Zbl0607.05031MR0865778
  8. Kratochvíl J., Matoušek J., Intersections graphs of segments, submitted. Zbl0808.68075
  9. Kratochvíl J., Matoušek J., NP-hardness results for intersection graphs, Comment. Math. Univ. Carolinae 30 (1989), 761-773. (1989) Zbl0697.05052MR1045907
  10. Middendorf M., Pfeiffer F., Max clique problem in classes of string graphs, preprint Univ. Bonn (1988). (1988) Zbl0764.68129MR1189857
  11. Sinden F. W., Topology of thin film RC circuits, Bell System Tech. J. (1966), 1639-1662. (1966) Zbl0144.45601
  12. Valiant L. G., Universality considerations in VLSI circuits, IEEE Trans. Comput. 30 (1981), 135-140. (1981) Zbl0455.94046MR0605722

NotesEmbed ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.